问题 C: 牛奶供应(三)

内存限制:128 MB 时间限制:1.000 S
评测方式:文本比较 命题人:
提交:31 解决:21

题目描述

小爱经营了一家牧场生产牛奶,接下来 n 天时间里,每天都有订单,其中第 i 天,必须发出 ��ai 箱牛奶。生产牛奶的成本来自于两方面:

  • 一是材料费。原料价格每天都会变化,如果选择在第i天生产牛奶,需要为每箱牛奶支付 ��ci 元的材料费。
  • 二是存储费。如果原材料成本上涨,可以提前把牛奶做好,放在冷库里保存,但需要支付仓储费,一箱牛奶存放一天的成本是 s 元。

每天的产能都没有上限,也就是说可以在任一天生产出任意多数量的牛奶,冷库的容量也没有上限,且假设牛奶可以存放任意长的时间。

请问,为了满足这些订单的要求,小爱应该如何规划每天的产量,又如何存储,才能把总成本控制到最小?

输入

第一行:两个整数 n 和 s
第二行到第 �+1n+1 行:第 �+1i+1 行有两个整数 ��ci 和 ��ai


  • 1s100,000
  • 1≤��≤100,0001ci100,000
  • 1≤��≤100,0001ai100,000
  • 对于 30%30% 的数据,1≤�≤201n20
  • 对于 60%60% 的数据,1≤�≤5,0001n5,000
  • 对于 100%100% 的数据,1≤�≤1,000,0001n1,000,000


输出

单个整数:表示为了满足所有订单的最小总成本。

样例输入 复制

3 10
100 5
200 5
90 20

样例输出 复制

2850

提示

第一天生产10箱,小计1000元
第二天不生产,用存货,支付存储费50元
第三天生产20箱


提示:
1. 枚举(考虑结构体),60%-80%分数
2. 递推是正解,有n种方式尝试:前缀和、递推、贪心等(乘法分配律)


Note1:从基础模拟代码可以优化为前缀和算法,累加第j天的单价*第i天的数量+仓储费用即可。