[USACO Mar03]奶酪工厂

成绩 0 开启时间 2013年01月21日 星期一 09:45
折扣 0.8 折扣时间 2013年01月21日 星期一 09:45
允许迟交 关闭时间 2013年01月21日 星期一 09:45
输入文件 factory.in 输出文件 factory.out

【问题描述】
     奶牛们开办了一个奶酪工厂来生产世界著名的约克奶酪。在接下来的 N (1<=N<=10000) 星期中,由于牛奶和劳动力的价格变化,奶酪的成本也在变化。因此奶酪工厂在第 i 个星期要花 C_i (1<=C_i<=5000) 分来生产一个单位的奶酪。 由于采用了最先进的技术,约克奶酪工厂在一个星期内可以生产任意多的奶酪。

约克奶酪工厂拥有一个无限大的仓库, 每个星期生产的多余的奶酪都会放在这里。而且每个星期存放一个单位的奶酪要花费 S (1<=S<=100) 分,不过幸运的是由于采用了最先进的技术,奶酪在仓库里不会坏 ^_^

工厂最近收到了客户 N 个星期的订单,第 i 个星期要向客户提供 Y_i (0<=Y_i<=10000) 个单位的奶酪。当然这些奶酪可以在第 i 个星期时生产,也可以从仓库中拿取。

采用怎么样的生产策略才会使约克工厂的花费最小呢?你能帮帮它们吗?


【输入格式】
     * 第 1 行两个整数: N 和 S

* 接下来的 N 行中,第 i 行的两个数表示: C_i 和 Y_i

【输出格式】
    * 输出仅一行,工厂生产的最小花费

【输入输出样例】
 
factory.in
4 5
88 200
89 400
97 300
91 500
factory.out
126900

【输入输出样例说明】
最佳生产方案如下:第一个星期生产 200 个单位的奶酪全部送给客户,第二个星期生产 700 个单位的奶酪, 400 个送给客户,另外 300 个放在仓库。第三个星期把仓库中的 300 个奶酪卖给客户,第四个星期生产 500 个单位的奶酪卖给客户。