Имеется n коров на числовой прямой. Расположение i-ой коровы задано числом xi, а вес i-ой коровы задан числом yi.

По сигналу Фермера Джона некоторые из коров формируют пары так, что

• Каждая пара состоит из двух различных коров a и b чьи расположения не далее k друг от друга, то есть |xa − xb| ≤ k.
• Каждая корова или является частью некоторой пары или не является частью некоторой пары.
• Группировка в пары называется максимальной, если никакие две из неспаренных коров не могут образовать пары.

Определите интервал возможных сумм весов неспаренных коров. А именно

• Если t = 1, вычислите минимально возможную сумму весов неспаренных коров.
• Если t = 2, вычислите максимально возможную сумму весов неспаренных коров.

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

Первая строка ввода содержит t, n (1 ≤ n ≤ 105), k (1 ≤ k ≤ 109).

В каждой из последующих n строк i-ая строка содержит xi (0 ≤ xi ≤ 109) и yi (1 ≤ yi ≤ 104). Гарантируется, что 0 ≤ x1 < x2 < ... < xn ≤ 109.

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

Выведите минимальную или максимальную возможные суммы весов неспаренных коров.

Пример 1

В этом примере коровы 2 и 4 могут быть спарены, поскольку расстояние между ними равно 2. Это оптимально, поскольку другие спаривания вообще не возможны: Коровы 1 и 3 находятся на расстоянии 3. Коровы 3 и 5 находятся на расстоянии 3. Коровы 1 и 5 находятся на расстоянии 6. Сумма весов неспаренных коров равна: 2 + 2 + 2 = 6.

Пример 2

Здесь коровы 1 и 2 могут быть спарены, поскольку они находятся на расстоянии 2 (≤ k). Коровы 4 и 5 также могут быть спарены, поскольку они также находятся на расстоянии 2 (≤ k). Последнее спаривание оптимально, т.к. неспаренной остаётся только корова 3, её вес 2.

Пример 3

Ответ для этого примера равен 693 + 992 + 785 = 2470.