Сегодня жаркий летний день, и корова Беси чувствует себя утомлённой. Она хочет так расположиться на поле, чтобы она находилась на коротком расстоянии от как можно большего количества вкусной травы.
Имеется N (1 <= N <= 100,000) участков травы на поле Беси, которое представляется числовой прямой. I-тый участок травы содержит gi единиц травы (1<=gi<=10,000) и находящихся в различных точках на расстоянии xi от начала поля (0 <= xi <= 1,000,000). Беси хочет выбрать на поле такую точку, (возможно некоторую точку из тех, что с травой), чтобы максимальное количество травы находилось на расстоянии не более K шагов от этой точки (1 <= K <= 2,000,000).
Пожалуйста, помогите Беси определить максимальное количество травы если она выберет наилучшее расположение этой точки.
PROBLEM NAME: lazy
Формат входных данных
* Строка 1: Два целых числа N и K.
* Строки 2..1+N: Строка i+1 описывает i-ый кусок травы, используя 2 Целых числа: gi и xi
Формат выходных данных
* Строка 1: Максимальное количество травы на расстоянии не превышающем K от оптимальной позиции Беси.
Примечание
Беси должна расположиться на позиции x=4, тогда количества травы, находящиеся в позициях x=1, x=2 и x=7 ,будут достижимы для неё.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 3
4 7
10 15
2 2
5 1
|
11
|