У парі (Платина)
n корів стоять в ряд на прямій, кожна з них належить до породи Holstein або Guernsey. Порода i-ї корови позначається як b[i] ∈ {H, G}, положення i-ї корови визначається значенням x[i], а вага i-ї корови — значенням y[i].
За сигналом Фермера Джона деякі корови утворюють пари за такими умовами:
Кожна пара складається з корів порід Holstein h і Guernsey g, чиї положення відрізняються не більше ніж на k; тобто, |
x[h]−x[g]| ≤ k.Кожна корова або входить до якоїсь пари, або залишається без пари.
Розбиття на пари є максимальним, якщо жодні з решти корів не можуть утворити пару.
Визначте діапазон можливих сум ваг корів, що не потрапили в пари:
Якщо t = 1, обчисліть мінімально можливу суму ваг неспарених корів.
Якщо t = 2, обчисліть максимально можливу суму ваг неспарених корів.
Вхідні дані
Перший рядок містить t, n (1 ≤ n ≤ 5000), k (1 ≤ k ≤ 10^9).
Далі йдуть n рядків, де i-й рядок містить bi, x[i] (0 ≤ x[i] ≤ 10^9), y[i] (1 ≤ y[i] ≤ 10^5). Гарантується, що 0 ≤ x[1] < x[2] < ... < x[n] ≤ 10^9.
Вихідні дані
Виведіть мінімальну або максимальну можливу суму ваг неспарених корів.
Приклад 1
Корови 2 і 3 можуть спаруватися, оскільки вони знаходяться на відстані 1, що менше k = 4. Це парування максимальне, оскільки корова 1 - єдина залишилася породи Guernsey, на відстані 5 від корови 4 і на відстані 7 від корови 5, що більше k = 4. Сума ваг неспарених корів 1 + 6 + 9 = 16.
Приклад 2
Корови 1 і 2 можуть спаруватися, оскільки знаходяться на відстані 2 ≤ k = 4, і корови 3 і 5 можуть спаруватися, оскільки вони знаходяться на відстані 4 ≤ k = 4. Це парування максимальне, оскільки залишиться тільки одна корова 4. Сума ваг буде сумою її ваги, рівно 6.
Приклад 3
Відповідь у цьому прикладі 18 + 465 + 870 + 540 = 1893.