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