4404. [CCPC 2026 HA] 塔尖最强机器人

Problem F. 尖塔最强机器人

Input file: $\verb|standard input|$

Output file: $\verb|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

1 3
4 1

11

7 3
4 2
0 0
0 0
0 0
0 0
0 0
0 0

27

Note

以第二个样例为例：

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