题目描述

光头强购买了一家世界闻名的森林蜂蜜工厂。在接下来的 $N(1≤N≤10000)$ 周内，劳动力的价格将每周波动，具体为：公司每周生产一单位蜂蜜的成本为 $C_i(1≤C_i≤5000)$ 元。

光头强拥有一个仓库，可以以每周每单位蜂蜜 $S(1≤S≤100)$ 元的固定费用储存未使用的蜂蜜。蜂蜜不会变质。光头强的仓库非常庞大，因此可以任意存放多个单位的蜂蜜。

光头强希望找到一种方法，每周向客户（自然是熊大熊二）交付 $Y_i(0≤Y_i≤10000)$ 单位的蜂蜜（$Y_i$ 是第 $i$ 周的交付量）。帮助光头强在整个 $N$ 周内将成本降至最低。第一周生产的蜂蜜，以及任何已经储存的蜂蜜，都可以用来满足光头强那一周的需求。

输入描述

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

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

输出描述

第 $1$ 行：第 $1$ 行包含一个整数：满足蜂蜜计划的最低总成本。请注意，总数可能超过32位整数。

4 5
88 200
89 400
97 300
91 500

126900

提示

在第 $1$ 周，生产 $200$ 单位蜂蜜并将其全部交付。在第 $2$ 周，生产 $700$ 单位蜂蜜：交付 $400$ 单位蜂蜜，同时储存 $300$ 单位蜂蜜。在第 $3$ 周，交付储存的 $300$ 个单元。在第 $4$ 周，生产并交付 $500$ 单位蜂蜜。