#P1376. [USACO05MAR] Yogurt factory 机器工厂

    ID: 420 远端评测题 1000ms 250MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>贪心福建省历届夏令营USACO2005

[USACO05MAR] Yogurt factory 机器工厂

题目描述

小 T 开办了一家机器工厂,在 NN个星期内,原材料成本和劳动力价格不断起伏,第 ii 周生产一台机器需要花费 CiC_i 元。若没把机器卖出去,每保养一台机器,每周需要花费 SS 元,这个费用不会发生变化。

机器工厂接到订单,在第 ii 周需要交付 YiY_i 台机器给委托人,第 ii 周刚生产的机器,或者之前的存货,都可以进行交付。

请你计算出这 nn 周时间内完成订单的最小代价。

输入格式

第一行输入两个整数 NNSS,接下来 NN 行每行两个数 CiC_iYiY_i

输出格式

输出一个整数,表示最少的代价。

4 5
88 200
89 400
97 300
91 500
126900

提示

1n1041\leq n\leq 10^41Ci50001 \le C_i \le 50001S1001 \le S\le 1000Yi1040\le Y_i\le 10^4