题目描述

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

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

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

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

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

输入格式

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

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

输出格式

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

样例

输入样例

4 5
88 200
89 400
97 300
91 500

输出样例

126900

提示

输出详情：

第一个月生产 200 吨酸奶；

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

第三个月不生产酸奶；

第三个月生产 500 吨