I. Лайки
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Светозар завёл себе канал на популярной видеоплатформе. Первое же видео имело огромный успех! В день $$$i$$$ оно получило $$$a_i$$$ лайков, где $$$a_i$$$ — неотрицательное целое число.

К сожалению, после очередной реорганизации веб-интерфейса по просьбам трудящихся платформа перестала отображать количество лайков в основном меню модерации канала. Теперь для получения полной статистики нужно нажимать очень много кнопок, а то и вовсе в поддержку обращаться!

Впрочем, Светозару пока не нужна полная статистика. У него сохранились $$$n$$$ доказательств того, что в конце дня $$$d_j$$$ общее количество лайков равнялось $$$s_j$$$ (для $$$j = 1, 2, \ldots, n$$$). Таким образом, $$$a_1 + a_2 + \ldots + a_{d_j} = s_j$$$.

Светозару интересно, сколько лайков могло быть за $$$T$$$ последовательных дней, если рассматривать только первые $$$d_n$$$ дней. Иными словами, необходимо найти максимальную теоретически возможную сумму $$$a_\ell + a_{\ell+1} + \ldots + a_{\ell+T-1}$$$ при условии $$$1 \leqslant \ell \leqslant d_n - T + 1$$$. Конечно, период из $$$T$$$ дней не обязан начинаться или заканчиваться непосредственно в дни $$$d_1, d_2, \ldots, d_n$$$, для которых данные уже есть.

Входные данные

Первая строка содержит два целых числа $$$n$$$ и $$$T$$$ ($$$1 \leqslant n \leqslant 2 \cdot 10^5$$$, $$$1 \leqslant T \leqslant 10^6$$$) — количество замеров и длина периода.

Следующие $$$n$$$ строк содержат по два целых числа $$$d_j$$$ и $$$s_j$$$ — день замера и общее количество лайков к концу этого дня. Гарантируется, что $$$d_n \geqslant T$$$, что $$$1 \leqslant d_1 \lt d_2 \lt \ldots \lt d_n \leqslant 10^6$$$ и что $$$1 \leqslant s_1 \leqslant s_2 \leqslant \ldots \leqslant s_n \leqslant 10^9$$$.

Выходные данные

Выведите одно целое число — максимально возможное количество лайков за $$$T$$$ последовательных дней.

Пример
Входные данные
3 2
2 4
4 9
6 12
Выходные данные
9
Примечание

В примере можно взять последовательность $$$(0, 4, 5, 0, 3, 0)$$$. Она согласуется со всеми замерами. За второй и третий дни получено $$$4 + 5 = 9$$$ лайков. Ни за какие два последовательных дня нельзя получить больше лайков.