H. 尖塔最强机器人
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

作为杀戮尖塔的最强角色，故障机器人拥有一个专属的机制——充能球。通过卡牌，故障机器人可以将生成的充能球放入充能球栏位中。在故障机器人的回合结束时，所有充能球会触发它们的被动效果；而在被消耗时，充能球也能产生爆发性的效果。

有一天，观者向故障机器人请教如何才能拥有极高的输出能力。于是，故障机器人向观者抛出了这样一个问题：

假设一局游戏共有 $$$n$$$ 个回合，而你有 $$$3$$$ 个初始为空的充能球栏位。在每个回合中，你有以下两种操作方式：

  • 打出"电击"：每回合你有 $$$a_i$$$ 张"电击"。每次打出一张"电击"时，若当前存在空的充能球栏位，则占用一个空位并生成一个闪电充能球；否则直接造成 $$$d$$$ 点伤害。
  • 打出"双重释放"：每回合你有 $$$b_i$$$ 张"双重释放"。每次打出一张"双重释放"时，若当前场上存在闪电充能球，则消耗一个闪电充能球并造成 $$$2d$$$ 点伤害，同时释放对应的栏位；否则无任何效果。

在每个回合内，你可以以任意顺序打出任意张"电击"和"双重释放"。回合结束时，若场上剩余 $$$x$$$ 个闪电充能球，则会额外造成 $$$x$$$ 点伤害，并且这些球会保留到下一回合，但手上剩余的"电击"和"双重释放"不会保留到下一回合。

作为杀戮尖塔第四弱的角色，观者无法解决这个问题，于是她向你求助，希望你能帮她计算出 $$$n$$$ 个回合内能造成的最大伤害。

Input

第一行输入两个整数 $$$n, d$$$ $$$(1 \le n, d \le 10^5)$$$，分别表示游戏的总回合数以及触发直接伤害或消耗伤害时的数值 $$$d$$$。

接下来 $$$n$$$ 行，第 $$$i$$$ 行输入两个整数 $$$a_i, b_i$$$ $$$(0 \le a_i, b_i \le 10^5)$$$，分别表示在第 $$$i$$$ 个回合中"电击"和"双重释放"的数量。

Output

输出一行一个整数，表示在 $$$n$$$ 个回合内能造成的最大伤害。

Examples
Input
1 3
4 1
Output
11
Input
7 3
4 2
0 0
0 0
0 0
0 0
0 0
0 0
Output
27
Note

以第二个样例为例：

在第一回合，先打出 $$$1$$$ 张"电击"，然后打出 $$$1$$$ 张"双重释放"消耗掉该球并造成 $$$6$$$ 点伤害。接着打出 $$$3$$$ 张"电击"获得 $$$3$$$ 个闪电充能球。在接下来的每个回合结束时，都会因为场上剩余 $$$3$$$ 个球而额外造成 $$$3$$$ 点伤害，共计 $$$27$$$ 点伤害。