题目描述

一座星港需要在接下来的 $N$ 周内持续获得能源单元。第 $i$ 周购买一个能源单元需要花费 $C_i$ 元，而该周必须向星港供应 $Y_i$ 个能源单元。能源单元按整数个购买，且每周可购买的数量不受限制。

能源单元可以在需要时当周购买，也可以提前购买并存入仓库。每储存一个能源单元一周，需要支付 $S$ 元保管费。所有需求都必须按时满足，并且不能使用未来购买的能源单元满足此前的需求。

请计算完成全部补给任务所需的最小总费用。

输入格式

第一行输入两个整数 $N$ 和 $S$。

接下来 $N$ 行，第 $i$ 行输入两个整数 $C_i$ 和 $Y_i$，分别表示第 $i$ 周的单位购买价格和需求量。

输出格式

输出一个整数，表示满足所有需求所需的最小总费用。

样例输入

4 5
88 200
89 400
97 300
91 500

样例输出

126900

数据范围

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