У парі (Платина)#11229

У парі (Платина)

2 секунди

512 мегабайтів

Легка

$n$ корів стоять в ряд на прямій, кожна з них належить до породи Holstein або Guernsey. Порода $i$ -ї корови позначається як $b_{i} \in {H, G}$ b_i \in \{H, G\}, положення $i$ -ї корови визначається значенням $x_{i}$ x_i, а вага $i$ -ї корови — значенням $y_{i}$ y_i.

За сигналом Фермера Джона деякі корови утворюють пари за такими умовами:

Кожна пара складається з корів порід Holstein $h$ і Guernsey $g$ , чиї положення відрізняються не більше ніж на $k$ ; тобто, $∣ x_{h} - x_{g} ∣ \leq k$ |x_h - x_g| \le k.
Кожна корова або входить до якоїсь пари, або залишається без пари.
Розбиття на пари є максимальним, якщо жодні з решти корів не можуть утворити пару.

Визначте діапазон можливих сум ваг корів, що не потрапили в пари:

Якщо $t = 1$ t = 1, обчисліть мінімально можливу суму ваг неспарених корів.
Якщо $t = 2$ t = 2, обчисліть максимально можливу суму ваг неспарених корів.

Вхідні дані

Перший рядок містить $t$ , $n$ ( $1 \leq n \leq 5000$ 1 \le n \le 5000), $k$ ( $1 \leq k \leq 1 0^{9}$ 1 \le k \le 10^9).

Далі йдуть $n$ рядків, де $i$ -й рядок містить $b_{i}$ b_i, $x_{i}$ x_i ( $0 \leq x_{i} \leq 1 0^{9}$ 0 \le x_i \le 10^9), $y_{i}$ y_i ( $1 \leq y_{i} \leq 1 0^{5}$ 1 \le y_i \le 10^5). Гарантується, що $0 \leq x_{1} < x_{2} < \dots < x_{n} \leq 1 0^{9}$ 0 \le x_1 < x_2 < \ldots < x_n \le 10^9.

Вихідні дані

Виведіть мінімальну або максимальну можливу суму ваг неспарених корів.

Приклади

Приклад 1

Приклад 2

Приклад 3

Примітка

У прикладі 1 корови $2$ і $3$ можуть спаруватися, оскільки вони знаходяться на відстані $1$ , що менше $k = 4$ k = 4. Це парування максимальне, оскільки корова $1$ — єдина, що залишилася, породи Guernsey, на відстані $5$ від корови $4$ і на відстані $7$ від корови $5$ , що більше $k = 4$ k = 4. Сума ваг неспарених корів $1 + 6 + 9 = 16$ 1 + 6 + 9 = 16.

У прикладі 2 корови $1$ і $2$ можуть спаруватися, оскільки знаходяться на відстані $2 \leq k = 4$ 2 \le k = 4, і корови $3$ і $5$ можуть спаруватися, оскільки вони знаходяться на відстані $4 \leq k = 4$ 4 \le k = 4. Це парування максимальне, оскільки залишиться тільки одна корова $4$ . Сума ваг неспарених корів — це вага єдиної неспареної корови, а саме $6$ .

У прикладі 3 відповідь $18 + 465 + 870 + 540 = 1893$ 18 + 465 + 870 + 540 = 1893.