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

[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