\(N\) (\(1\le N\le 5000\)) корів стоять у ряд на прямий, кожна з них має породу Holstein чи Guernsey. Порода \(i\)-ої корови задається значенням \(b_i\in \{H,G\}\), Положення \(i\)-ої корови задається величиною \(x_i\) (\(0 \leq x_i \leq 10^9\)), а вага \(i\)-ої корови задається величиною \(y_i\) (\(1 \leq y_i \leq 10^5\)).

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

• Кожна пара складається з корів порід Holstein \(h\) і Guernsey \(g\) чиї положення лише на \(K\) друг від друга (\(1\le K\le 10^9\)); тобто \(|x_h-x_g|\le K\).
• Кожна корова або частина якоїсь пари, або не входить у жодну пару.
• Розбиття на пари є максимальним якщо жодні з корів, що залишилися, не можуть утворити пару.

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

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

Формат вихідних даних

Перший рядок введення містить \(T\), \(N\), \(K\).

Далі слідують \(N\) рядків, \(i\)-а з яких містить числа \(b_i,x_i,y_i\). Гарантується, що \(0\le x_1< x_2< \cdots< x_N\le 10^9\).

Приклад вхідних даних-1

2 5 4
G 1 1
H 3 4
G 4 2
H 6 6
H 8 9

Приклад вихідних даних-1

16

Пояснення до прикладу-1

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

Приклад вхідних даних-2

1 5 4
G 1 1
H 3 4
G 4 2
H 6 6
H 8 9

Приклад вихідних даних-2

6

Пояснення до прикладу-2

Корови \(1\) і \(2\) можуть спаровуватися, оскільки знаходяться на відстані \(2 \leq K = 4\), і корови \(3\) і \(5\) можуть спаровуватись, оскільки вони знаходяться на відстані \(4 \leq K = 4\). Це парування максимальне, оскільки залишиться лише одна корова \(4\) . Сума ваг буде сума її ваги, дорівнює \(6\).

Приклад вхідних даних-3

2 10 76
H 1 18
H 18 465
H 25 278
H 30 291
H 36 202
G 45 96
G 60 375
G 93 941
G 96 870
G 98 540

Приклад вихідних даних-3

1893

Пояснення до прикладу-3

Відповідь у цьому прикладі \(18+465+870+540=1893\).

Примітка: межа пам'яті для цього завдання 500MB.

Оцінювання

• У тестах 1-7 \(N,K\le 1000\).
• У тестах 8-19 немає додаткових обмежень.