Кефа хочет отметить свой первый крупный заработок походом в ресторан. Однако ему нужна компания.
У Кефы есть n друзей, каждый из которых согласится пойти в ресторан, если Кефа попросит. Каждый друг характеризуется количеством денег у него и степенью дружбы с Кефой. Наш попугай не хочет, чтобы какой-то друг почувствовал себя бедным по сравнению с кем-то другим в компании (Кефа не в счет). Друг чувствует себя бедным, если в компании есть кто-то, у кого денег хотя бы на d единиц больше, чем у него. Также Кефа хочет, чтобы суммарная степень дружбы членов компании была максимальной. Помогите ему пригласить оптимальную компанию!
Выходные данные
Выведите максимальную суммарную степень дружбы, которой можно добиться.
Примечание
В первом тесте из условия выгоднее всего сформировать компанию только из второго друга. При всех других вариантах суммарная степень дружбы будет меньше.
Во втором тесте из условия мы можем взять всех друзей.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 5
75 5
0 100
150 20
75 1
|
100
|
|
2
|
5 100
0 7
11 32
99 10
46 8
87 54
|
111
|