C. Коровоконг покупает колоду карт
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Коровоконга уже есть много колод карт, но в этот раз он увидел в магазине совершенно новую колоду из n красных и синих карт и сразу захотел её купить. Чтобы это сделать, придётся сыграть в игру с владельцем магазина.

Игра состоит из последовательных ходов Коровоконга, на каждом ходу он совершает ровно одно из двух действий:

  • Взять фишки. Коровоконг получает 1 красную фишку и 1 синюю фишку (таким образом, в сумме он получает 2 фишки за одно действие).
  • Покупка одной карты. Коровоконг выбирает какую-то карту и покупает её за фишки по правилам, описанным ниже.

Базовая стоимость i-й карты составляет ri красных фишек и bi голубых фишек. Допустим, у Коровоконга сейчас есть A красных карт и B синих карт, тогда покупка i-й карты потребует от Коровоконга max(ri - A, 0) красных фишек и max(bi - B, 0) синих фишек. Обратите внимание, при покупке у Коровоконга забирают соответствующее количество фишек, но сами карты всегда остаются с ним. Каждую карту можно купить ровно один раз.

По данному описанию всех карт в колоде определите минимальное количество ходов, за которое Коровоконг может купить их все.

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

В первой строке входных данных записано целое число n (1 ≤ n ≤ 16).

В следующих n строках записаны параметры ci, ri и bi, где ci является символом «R» или «B», означающих красный или синий цвет карты соответственно. ri и bi (0 ≤ ri, bi ≤ 107) означают количество красных и синих фишек (соответственно) в базовой стоимости i-й карты.

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

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

Примеры
Входные данные
3
R 0 1
B 1 0
R 1 1
Выходные данные
4
Входные данные
3
R 3 0
R 2 0
R 1 0
Выходные данные
6
Примечание

В первом примере Коровоконгу потребуется совершить четыре хода:

  1. Взять фишки.
  2. Приобрести карту 1.
  3. Приобрести карту 2.
  4. Приобрести карту 3.
Обратите внимание, что на четвёртом ходу Коровоконг может купить карту 3, потому что у него уже есть одна красная и одна синяя карты и ему вообще не нужны фишки.

Во втором примере следующая стратегия будет одной из оптимальных:

  1. Взять фишки.
  2. Взять фишки.
  3. Приобрести карту 2.
  4. Взять фишки.
  5. Приобрести карту 3.
  6. Приобрести карту 1.
На пятом ходу, хотя у Коровоконга есть в запасе красная фишка, нет необходимости её тратить, потому что у него уже имеется красная карта.