Имеется n коров на числовой прямой. Расположение i-ой коровы задано числом x[i]
, а вес i-ой коровы задан числом y[i]
.
По сигналу Фермера Джона некоторые из коров формируют пары так, что
Каждая пара состоит из двух различных коров a и b чьи расположения не далее k друг от друга, то есть |x[a]
− x[b]
| ≤ k.
Каждая корова или является частью некоторой пары или не является частью некоторой пары.
Группировка в пары называется максимальной, если никакие две из неспаренных коров не могут образовать пары.
Определите интервал возможных сумм весов неспаренных коров. А именно
Если t = 1, вычислите минимально возможную сумму весов неспаренных коров.
Если t = 2, вычислите максимально возможную сумму весов неспаренных коров.
Первая строка ввода содержит t, n (1 ≤ n ≤ 10^5
), k (1 ≤ k ≤ 10^9
).
В каждой из последующих n строк i-ая строка содержит x[i]
(0 ≤ x[i]
≤ 10^9
) и y[i]
(1 ≤ y[i]
≤ 10^4
). Гарантируется, что 0 ≤ x[1]
< x[2]
< ... < x[n]
≤ 10^9
.
Выведите минимальную или максимальную возможные суммы весов неспаренных коров.
В этом примере коровы 2 и 4 могут быть спарены, поскольку расстояние между ними равно 2. Это оптимально, поскольку другие спаривания вообще не возможны: Коровы 1 и 3 находятся на расстоянии 3. Коровы 3 и 5 находятся на расстоянии 3. Коровы 1 и 5 находятся на расстоянии 6. Сумма весов неспаренных коров равна: 2 + 2 + 2 = 6.
Здесь коровы 1 и 2 могут быть спарены, поскольку они находятся на расстоянии 2 (≤ k). Коровы 4 и 5 также могут быть спарены, поскольку они также находятся на расстоянии 2 (≤ k). Последнее спаривание оптимально, т.к. неспаренной остаётся только корова 3, её вес 2.
Ответ для этого примера равен 693 + 992 + 785 = 2470.