1659: 奶酪工厂

内存限制:128 MB 时间限制:1.000 S 标准输入输出
题目类型:传统 评测方式:文本比较 上传者:
提交:23 通过:16

题目描述

奶牛们收购了一个奶酪工厂。
接下来的 N 个星期里, 牛奶价格和劳力价格不断起伏. 第 i 周, 生产一个单位奶酪需
要 Ci 便士. 工厂有一个货栈, 保存一单位奶酪, 每周需要 S 便士, 这个费用不会变化, 货
栈十分强大, 可以存无限量的奶酪, 而且保证它们不变质.
工厂接到订单, 在第 i 周需要交付 Yi 单位的奶酪给委托人, 第 i 周刚生产的奶酪, 以
及之前的存货, 都可以作为产品交付。
请帮牛们计算这段时间里完成任务的最小代价.

输入格式

第 1 行输入两个整数 N 和 S;
接下来 N 行, 输入 Ci 和 Yi;

输出格式

输出共一行一个整数, 最少的代价;

输入样例 复制

4 5
88 200
89 400
97 300
91 500

输出样例 复制

126900

数据范围与提示

【 样例解释】 第 1 周生产 200 单位奶酪并全部交付; 第 2 周生产 700 单位, 交付 400 单
位, 存 300 单位; 第 3 周交付 300 单位存货, 第 4 周生产并交付 500 单位.
【 数据规模】
对于 50%的数据: 1≤N≤10;
对于 70%的数据: 1≤N≤1,000;
对于 100%的数据: 1≤N≤10,000; 1≤S≤100; 1≤Ci≤5,000; 0≤Yi≤10,000;

分类标签