描述

奶牛们买下了一家酸奶工厂，生产世界闻名的 Yucky Yogurt。在接下来的 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 当周的需求。

输入

• 第 1 行：两个以空格分隔的整数 N 和 S。

• 第 2..N+1 行：第 i+1 行包含两个以空格分隔的整数：C_i 和 Y_i。

输出

• 第 1 行：第 1 行包含一个整数：满足酸奶计划的最低总成本。请注意，对于 32 位整数，总数可能太大。

输入数据 1

4 5
88 200
89 400
97 300
91 500

输出数据 1

126900

提示

输出详细信息：

在第 1 周，生产 200 单位酸奶并交付所有酸奶。 在第 2 周，生产 700 件商品：配送 400 件商品，同时储存 300 件商品。 在第 3 周，配送已储存的 300 件商品。在第 4 周，生产并交付 500 个单位。