你有 $n$ 个立方体积木，编号从 $1$ 到 $n$。第 $i$ 号积木的尺寸为 $a_i \times a_i \times a_i$，且表面印有图案 $w_i$（图案由整数标识）。

你的目标是使用选定的积木搭建一座塔，使其得分尽可能高。塔由若干个积木平放堆叠而成。设 $j_1, \dots, j_m$ 为按从底到顶顺序选出的积木编号（$m$ 为选出的积木数量）。塔的得分根据以下标准计算：

• 稳定性：如果每个上方的积木都比下方的积木小，即 $a_{j_x} > a_{j_{x+1}}$，则塔是稳定的。不稳定的塔得分为 $0$，无论其他标准如何。
• 高度：如果塔的高度为 $h = a_{j_1} + \dots + a_{j_m}$，则得分增加 $h$。
• 风格分：相邻积木的图案不同（即 $w_{j_x} \neq w_{j_{x+1}}$）会破坏美感，因此每出现一对这样的相邻积木，得分减少 $c$。

输入格式

输入的第一行包含两个整数 $n$ 和 $c$ ($1 \le n, c \le 500\,000$)，分别表示可用积木的数量和相邻积木图案不同时的惩罚值。

接下来的 $n$ 行描述了各个积木。第 $i$ 号积木的描述位于第 $i$ 行，包含两个整数 $a_i$ 和 $w_i$ ($1 \le a_i, w_i \le 500\,000$)，分别表示立方体积木的边长和图案编号。积木按尺寸非递减顺序给出，即 $a_i \le a_{i+1}$。

在分值为 $5$ 分的测试点中，额外满足 $a_i < a_{i+1}$。

输出格式

输出一个整数，表示用给定的积木所能搭建的塔的最高得分。

样例

样例输入 1

4 1
1 1
3 2
4 3
4 1

样例输出 1

6

样例输入 2

4 5
1 1
3 2
4 3
4 1

样例输出 2

5

说明

图 1：两组测试中的积木集合相同。测试仅在惩罚值 c 上有所不同。第一个测试中 c = 1，第二个测试中 c = 5。

图 2：第一个测试的最佳塔。高度为 8，有两次惩罚。得分为 8 - 2 · 1 = 6。对于 c = 5 的情况，该塔的得分为 8 - 2 · 5 = -2。

图 3：第二个测试的最佳塔。高度为 5，没有惩罚，因为积木具有相同的图案。得分为 5 - 0 · c = 5。