OpenJudge

50:★☆☆☆☆酸奶工厂

总时间限制:
1000ms
内存限制:
100000kB
描述

奶牛经营了一家酸奶工厂,生意非常红火。在接下去的 N 个月里,第 i 个月需要向社会提供 Ai吨酸奶。酸奶的生产受到很多因素的影响,所以每个月的生产成本是变化的,其中第 i 个月的成本是 每吨 Ci元。 奶牛可以提前里把酸奶做好,存在仓库里,等需要的时候再拿出来卖。存储在仓库里的酸奶,每 吨酸奶存放一个月需要支付 S 元的维护费用,存放的时间可以任意长。假设工厂的产量是无限的,存 储酸奶的仓库也是无限大的。请问为了满足订单的需要,奶牛生产这些酸奶最少要花多少钱?

输入
第一行:两个整数 N 和 S,1 ≤ N ≤ 10000, 1 ≤ S ≤ 100
第二行到第 N + 1 行:第 i + 1 行有两个整数 Ci 和 Ai,1 ≤ Ci ≤ 5000, 1 ≤ Ai ≤ 10000
输出
单个整数:表示生产酸奶的最小总费用
样例输入
4 5 
88 200 
89 400 
97 300 
91 500
样例输出
126900
提示
解释
第一个月生产 200 吨酸奶;第二个月生产 700 吨酸奶,并存下 300 吨;第三个月不生产酸 奶;第三个月生产 500 吨
来源
Yogurt factory, 2005 Mar

加油

全局题号
12597
添加于
2017-01-11
提交次数
75
尝试人数
22
通过人数
20