D. Мобильная скам-реклама
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Рассмотрим следующую игру.

В этой игре уровень состоит из $$$n$$$ пар ворот. Каждая пара содержит одни левые ворота и одни правые ворота. Каждые ворота выполняют одну из двух операций:

  • Операция сложения (+ a): Увеличивает количество людей в полосе на постоянную величину $$$a$$$.
  • Операция умножения (x a): Умножает текущее количество людей в полосе на целое число $$$a$$$. Это означает, что количество людей увеличивается на текущее количество людей в этой полосе, умноженное на $$$(a - 1)$$$.

Дополнительные люди, полученные от каждой операции, могут быть распределены по любой полосе. Однако люди, уже находящиеся в полосе, не могут быть перемещены в другую полосу.

Изначально в каждой полосе находится один человек. Ваша задача — определить максимальное общее количество людей, которое можно достичь к концу уровня.

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

Первая строка содержит целое число $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — количество наборов входных данных.

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \leq n \le 30$$$) — количество пар ворот.

Следующие $$$n$$$ строк каждого набора входных данных содержат информацию сначала о левых воротах, а потом о правых воротах. Информация о воротах представлена в виде + $$$a$$$ ($$$1 \le a \le 1000$$$) или x $$$a$$$ ($$$2 \le a \le 3$$$) для некоторого целого числа $$$a$$$.

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

Для каждого набора входных данных выведите одно целое число — максимальное общее количество людей в конце уровня.

Пример
Входные данные
4
3
+ 4 x 2
x 3 x 3
+ 7 + 4
4
+ 9 x 2
x 2 x 3
+ 9 + 10
x 2 + 1
4
x 2 + 1
+ 9 + 10
x 2 x 3
+ 9 x 2
5
x 3 x 3
x 2 x 2
+ 21 + 2
x 2 x 3
+ 41 x 3
Выходные данные
32
98
144
351
Примечание

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

Изначально у нас $$$l=1$$$ человек в левой полосе и $$$r=1$$$ человек в правой полосе.

После прохождения первой пары ворот мы получаем $$$4$$$ человека от левых ворот и $$$1 \cdot (2-1) = 1$$$ человека от правых ворот, в сумме $$$4+1=5$$$ человек. Мы распределяем $$$2$$$ человека в левую полосу и $$$3$$$ человека в правую полосу. В результате в левой полосе $$$l=1+2=3$$$ человека, а в правой полосе $$$r=1+3=4$$$ человека.

После прохождения второй пары ворот мы получаем $$$3 \cdot (3-1) = 6$$$ человек от левых ворот и $$$4 \cdot (3-1) = 8$$$ человек от правых ворот, в сумме $$$6+8=14$$$ человек. Мы распределяем $$$7$$$ человек в левую полосу и $$$7$$$ человек в правую полосу. В результате в левой полосе $$$l=3+7=10$$$ человек, а в правой полосе $$$r=4+7=11$$$ человек.

После прохождения последней пары ворот мы получаем $$$7$$$ человек от левых ворот и $$$4$$$ человека от правых ворот, в сумме $$$7+4=11$$$ человек. Мы распределяем $$$6$$$ человек в левую полосу и $$$5$$$ человек в правую полосу. В результате в левой полосе $$$l=10+6=16$$$ человек, а в правой полосе $$$r=11+5=16$$$ человек.

В конце общее количество людей составляет $$$16+16=32$$$.