问题 E: 牛奶供应（三）
传统题
1.000s
时间限制
256MB
内存限制
22 提交
10 解决
【题目描述】
题目描述
小爱经营了一家牧场生产牛奶，接下来 n
天时间里，每天都有订单，其中第 i 天，必须发出 ai
箱牛奶。生产牛奶的成本来自于两方面：
一是材料费。原料价格每天都会变化，如果选择在第 i 天生产牛奶，需要为每箱牛奶支付 ci
元的材料费。
二是存储费。如果原材料成本上涨，可以提前把牛奶做好，放在冷库里保存，但需要支付仓储费，一箱牛奶存放一天的成本是 s 元。
牧场产量没有上限，可以在任何一天生产出任意多数量的牛奶，冷库的容量也是无限大的，假设牛奶可以存放任意长的时间。请问，为了满足这些订单的要求，小爱应该如何规划每天的产量，又如何存储，才能把总成本控制到最小？
输入格式
第一行：两个整数 n 和 s。
第二行到第 n+1
行：第 i+1
行有两个整数 ci
和 ai
。
输出格式
单个整数：表示为了满足所有订单的最小总成本。
数据范围
1≤s≤100,000
；
1≤ci≤100,000
；
1≤ai≤100,000
；
对于 30% 的数据，1≤n≤20
；
对于 60% 的数据，1≤n≤5,000
；
对于 100% 的数据，1≤n≤1,000,000
。
样例数据
输入:
3 10
100 5
200 5
90 20
输出:
2850
说明:
第一天生产10箱，小计1000元
第二天不生产，用存货，支付存储费50元
第三天生产20箱