У Коровоконга уже есть много колод карт, но в этот раз он увидел в магазине совершенно новую колоду из n красных и синих карт и сразу захотел её купить. Чтобы это сделать, придётся сыграть в игру с владельцем магазина.
Игра состоит из последовательных ходов Коровоконга, на каждом ходу он совершает ровно одно из двух действий:
- Взять фишки. Коровоконг получает 1 красную фишку и 1 синюю фишку (таким образом, в сумме он получает 2 фишки за одно действие).
- Покупка одной карты. Коровоконг выбирает какую-то карту и покупает её за фишки по правилам, описанным ниже.
Базовая стоимость i-й карты составляет ri красных фишек и bi голубых фишек. Допустим, у Коровоконга сейчас есть A красных карт и B синих карт, тогда покупка i-й карты потребует от Коровоконга max(ri - A, 0) красных фишек и max(bi - B, 0) синих фишек. Обратите внимание, при покупке у Коровоконга забирают соответствующее количество фишек, но сами карты всегда остаются с ним. Каждую карту можно купить ровно один раз.
По данному описанию всех карт в колоде определите минимальное количество ходов, за которое Коровоконг может купить их все.
Выходные данные
Выведите одно целое число, означающее минимальное количество ходов, за которое можно получить все карты колоды.
Примечание
В первом примере Коровоконгу потребуется совершить четыре хода:
- Взять фишки.
- Приобрести карту 1.
- Приобрести карту 2.
- Приобрести карту 3.
Обратите внимание, что на четвёртом ходу Коровоконг может купить карту
3, потому что у него уже есть одна красная и одна синяя карты и ему вообще не нужны фишки.
Во втором примере следующая стратегия будет одной из оптимальных:
- Взять фишки.
- Взять фишки.
- Приобрести карту 2.
- Взять фишки.
- Приобрести карту 3.
- Приобрести карту 1.
На пятом ходу, хотя у Коровоконга есть в запасе красная фишка, нет необходимости её тратить, потому что у него уже имеется красная карта.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
R 0 1
B 1 0
R 1 1
|
4
|
|
2
|
3
R 3 0
R 2 0
R 1 0
|
6
|