[Usaco2005 mar]Yogurt factory 奶酪工厂

奶酪工厂计划在接下来的 $N$ 周内生产奶酪。由于牛奶和劳动力价格不断变化，第 $i$ 周生产一个单位奶酪需要花费 $C_i$ 便士。

工厂拥有一个容量无限的仓库。每储存一个单位奶酪一周，需要支付 $S$ 便士的仓储费，且奶酪在储存期间不会变质。第 $i$ 周，工厂需要向客户交付 $Y_i$ 个单位的奶酪。工厂每周可以生产任意数量的奶酪，当周生产的奶酪和此前储存的奶酪均可用于完成当周的交付任务。

请计算在这 $N$ 周内完成所有交付任务所需的最小总费用。

输入格式

第一行包含两个以空格分隔的整数 $N$ 和 $S$，分别表示总周数和每单位奶酪每周的仓储费用。

接下来 $N$ 行，第 $i$ 行包含两个以空格分隔的整数 $C_i$ 和 $Y_i$，分别表示第 $i$ 周生产一个单位奶酪的费用和该周需要交付的奶酪数量。

输出格式

输出一个整数，表示完成所有交付任务所需的最小总费用。

答案可能超出 $32$ 位整数的表示范围。

样例输入

4 5
88 200
89 400
97 300
91 500

样例输出

126900

样例解释

第 $1$ 周生产 $200$ 个单位的奶酪并全部交付。

第 $2$ 周生产 $700$ 个单位的奶酪，其中 $400$ 个单位用于当周交付，剩余 $300$ 个单位存入仓库。

第 $3$ 周使用库存中的 $300$ 个单位完成交付。

第 $4$ 周生产并交付 $500$ 个单位的奶酪。

由此得到最小总费用 $126900$ 便士。

数据范围

• $1\le N\le 10^4$；
• $1\le S\le 100$；
• $1\le C_i\le 5\times 10^3$；
• $0\le Y_i\le 10^4$。

来源与许可

本题为 USACO 2005 March 试题「奶酪工厂」，题面与测试数据整理自 BZOJ。

样例 1

输入

4 5
88 200
89 400
97 300
91 500

输出

126900