n коров стоят в ряд на прямой, каждая из них имеет породу Holstein или Guernsey. Порода i-ой коровы задаётся значением bi ∈ {H, G}, Положение i-ой коровы задаётся величиной xi, а вес i-ой коровы задаётся величиной yi.

По сигналу Фермера Джона некоторые из коров образуют пары так, что

• Каждая пара состоит из коров пород Holstein h и Guernsey g чьи положения не более чем на k друг от друга; то есть, |xh − xg| ≤ k.
• Каждая корова или часть какой то пары, или не входит ни в какую пару.
• Разбиение на пары является максимальным если никакие из оставшихся коров не могут образовать пару.

Определите диапазон возможных сумм весов коров не попавших в пары, а именно

• Если t = 1, вычислите минимально возможную сумму весов неспаренных коров.
• Если t = 2, вычислите максимально возможную сумму весов неспаренных коров.

Входные данные

Первая строка содержит t, n (1 ≤ n ≤ 5000), k (1 ≤ k ≤ 109).

Далее следуют n строк, i-ая из которых содержит числа bi, xi (0 ≤ xi ≤ 109), yi (1 ≤ yi ≤ 105). Гарантируется, что 0 ≤ x1 < x2 < ... < xn ≤ 109.

Выходные данные

Выведите минимальную или максимальную возможную сумму весов неспаренных коров.

Пример 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.