\(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\), вычислите максимально возможную сумму весов неспаренных коров.
ФОРМАТ ВВОДА (с клавиатуры / stdin):
Первая строка ввода содержит
\(T\),
\(N\),
\(K\).
Далее следуют \(N\) строк, \(i\)-ая из которых содержит числа \(b_i,x_i,y_i\).
Гарантируется, что \(0\le x_1< x_2< \cdots< x_N\le 10^9\).
ФОРМАТ ВЫВОДА (на экран / stdout):
Минимальную или максимальную возможную сумму весов неспаренных коров.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2 5 4
G 1 1
H 3 4
G 4 2
H 6 6
H 8 9
|
16
|