题目描述

奶牛们购买了一家生产世界闻名的难吃酸奶的酸奶厂。在接下来的 ${N (1 <= N <= 10,000) }$周内，牛奶和劳动力的价格将每周波动，因此公司 ${C_i (1 <= C_i <= 5,000) }$美分每周生产一单位酸奶一世。

${Yucky }$的工厂设计精良，每周可以生产任意多单位的酸奶。 ${Yucky Yogurt }$拥有一个仓库，可以以每周每单位酸奶 ${S (1 <= S <= 100) }$美分的固定费用存储未使用的酸奶。

幸运的是，酸奶不会变质。 ${Yucky Yogurt }$的仓库很大，可以存放任意数量的酸奶。 ${Yucky }$想找到一种方法，每周向其客户交付 ${Y_i (0 <= Y_i <= 10,000) }$单位酸奶（${Y_i }$是第 ${i }$周的交付数量）。帮助 ${Yucky }$在整个 ${N }$周期间最大限度地降低成本。第 ${i }$周生产的酸奶以及任何已 经储存的酸奶都可以用来满足 ${Yucky }$在该周的需求。

酸奶的生产受到很多因素的影响，所以每个月的生产成本是变化的，其中第 ${i }$个月的成本是每吨 ${Ci }$元。奶牛可以提前里把酸奶做好存在仓库里，等需要的时候再拿出来卖。存储在仓库里的酸奶，每吨酸奶存放一个月需要支付 ${S }$元的维护费用，存放的时间可以任意长.假设工厂的产量是无限的，存储酸奶的仓库也是无限大的。

请问为了满足订单的需要，奶牛生产这些酸奶最少要花多少钱？

输入格式

第一行：两个整数 ${N }$和 ${S，}$${1 ≤}$ ${N ≤}$ ${10000, 1 ≤}$ ${S ≤}$ ${100}$

第二行到第 ${N + 1 }$行：第 ${i + 1 }$行有两个整数 ${Ci }$和 ${A_i，}$${1 ≤}$ ${C_i ≤}$ ${5000, 1 ≤}$ ${A_i ≤}$ ${10000}$

输出格式

单个整数：表示生产酸奶的最小总费用

样例

输入样例

4 5
88 200
89 400
97 300
91 500

输出样例

126900

提示

输出详情：

第一个月生产 200 吨酸奶；

第二个月生产700 吨酸奶，并存下 300 吨；

第三个月不生产酸奶；

第三个月生产 500 吨