#181. 奶酪工厂

奶酪工厂

奶牛们收购了一个奶酪工厂,接下来的 (1N10000)(1≤N≤10000) 个星期里,牛奶价格和劳力价格不断起伏。第 ii 周,生产一个单位奶酪需要 Ci(1Ci5000)C_i (1≤C_i≤5000)便士。

工厂有一个货栈,保存一单位奶酪,每周需要 S(1S100)S (1≤S≤100) 便士,这个费用不会变化。货栈十分强大,可以存无限量的奶酪,而且保证它们不变质。

工厂接到订单,在第 ii 周需要交付 Yi(0Yi104)Y_i (0≤Y_i≤10^4) 单位的奶酪给委托人。第 ii 周刚生产的奶酪,以及之前的存货,都可以作为产品交付。请帮牛们计算这段时间里完成任务的最小代价.

输入格式

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

输出格式

一个整数,表示最少的成本,答案可能会超过 2322^{32} 整数范围。

样例解释

  • 第 1 周生产 200 单位奶酪并全部交付;
  • 第 2 周生产 700 单位,交付 400 单位,剩下 300 单位;
  • 第 3 周交付 300 单位存货;
  • 第 4 周生产并交付 500 单位。

输出时每行末尾的多余空格,不影响答案正确性

要求使用「文件输入输出」的方式解题,输入文件为 yogurt.in,输出文件为 yogurt.out

样例输入

4 5
88 200
89 400
97 300
91 500

样例输出

126900