TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P3878
  • 题目
  • P3878榴莲罐头
    限制 : 时间限制 : - MS   空间限制 : 165536 KB
    评测说明 : 1s
    问题描述

    小郭同学的生日快到了, 她打算用N天来庆祝。 编程班的同学们的最近注意力不太集中, 因此小郭想提供大家最喜欢的榴莲罐头来使大家高兴。她已经计算出了第i天需要的罐头数为Xi。    

    小郭的学校提供了许多服务给编程班的同学们, 包括一个出售食品的小卖部。小卖部出售的榴莲罐头价格是起伏不定的,第i天,榴莲罐头的价格是Wi块钱一罐。小郭同学每天可以购买任意数量的罐头,这些罐头可以立即发给同学们享用,也可以寄存在小卖部里,小郭同学随时可以把它们取出来。寄存一个罐头的花费是k块钱一天。
        小郭同学想知道,她最少需要花费多少钱就能满足每天罐头的需求。

    输入格式

    第一行输入两个整数N和K, N表示庆祝活动持续N天,K为一个罐头寄存一天的花费。

    接下来有N行,每行输入两个整数Wi和Xi。 Wi表示第i天购买一个罐头的费用,Xi表示第i天需要的罐头数量。

    输出格式

    输出一个整数,表示小郭同学所需花费的最少费用。结果可能很大,mod 100000007后再输出。

    提示

    【样例1解释】

    共有3天,寄存的费用为每天3元
    第1天一共购买2个罐头共花费1*2=2元;
    第2天购买4个罐头共花费3*4=12元;
    第3天不购买罐头,改用第2天多购买的2个罐头,共花费2*3=6元的寄存费用。

    总花费2+12+6=20元。

    【数据范围】

    对于30%的数据,1<=N<=100, 0<=K<=100。

    对于70%的数据,1<=N<=5000, 0<=K<=1000。

    对于100%的数据,1<=N<=1000000, 0<=K<=10000, 0<=Wi,Xi<=50000。