3097: 牛奶供应（三）
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：28
解决：19
题目描述
小爱经营了一家牧场生产牛奶，接下来 �n 天时间里，每天都有订单，其中第 �i 天，必须发出 ��ai 箱牛奶。生产牛奶的成本来自于两方面：
- 一是材料费。原料价格每天都会变化，如果选择在第�i天生产牛奶，需要为每箱牛奶支付 ��ci 元的材料费。
- 二是存储费。如果原材料成本上涨，可以提前把牛奶做好，放在冷库里保存，但需要支付仓储费，一箱牛奶存放一天的成本是 �s 元。
每天的产能都没有上限，也就是说可以在任一天生产出任意多数量的牛奶，冷库的容量也没有上限，且假设牛奶可以存放任意长的时间。
请问，为了满足这些订单的要求，小爱应该如何规划每天的产量，又如何存储，才能把总成本控制到最小？
输入
第一行：两个整数 �n 和 �s。
第二行到第 �+1n+1 行：第 �+1i+1 行有两个整数 ��ci 和 ��ai。
第二行到第 �+1n+1 行：第 �+1i+1 行有两个整数 ��ci 和 ��ai。
- 1≤s≤100,000；
- 1≤��≤100,0001≤ci≤100,000；
- 1≤��≤100,0001≤ai≤100,000；
- 对于 30%30% 的数据，1≤�≤201≤n≤20；
- 对于 60%60% 的数据，1≤�≤5,0001≤n≤5,000；
- 对于 100%100% 的数据，1≤�≤1,000,0001≤n≤1,000,000。
输出
单个整数：表示为了满足所有订单的最小总成本。
样例输入 复制
3 10
100 5
200 5
90 20样例输出 复制
2850提示
第一天生产10箱，小计1000元
第二天不生产，用存货，支付存储费50元
第三天生产20箱
提示：
1. 枚举(考虑结构体)，60%-80%分数
2. 递推是正解，有n种方式尝试：前缀和、递推、贪心等（乘法分配律）
Note1：从基础模拟代码可以优化为前缀和算法，累加第j天的单价*第i天的数量+仓储费用即可。
第二天不生产，用存货，支付存储费50元
第三天生产20箱
提示：
1. 枚举(考虑结构体)，60%-80%分数
2. 递推是正解，有n种方式尝试：前缀和、递推、贪心等（乘法分配律）
Note1：从基础模拟代码可以优化为前缀和算法，累加第j天的单价*第i天的数量+仓储费用即可。