У вас есть $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

6

Пример 2

4 5
1 1
3 2
4 3
4 1

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.