D. 欺诈游戏广告

时间与内存限制

• 时间限制：$3$ 秒
• 内存限制：$256$ MB

题意翻译

考虑下面这个游戏：

一个关卡由 $n$ 对门组成。每一对包含一扇左门和一扇右门。每扇门会执行以下两种操作之一：

1. 加法操作 $+ \ a$：让当前通道的人数增加常数 $a$。
2. 乘法操作 $\times \ a$：让当前通道的人数乘以整数 $a$。等价于人数增加 $(a-1) \times$ 当前人数。

每次操作新增的所有人，都可以自由分配到左通道或右通道。 但是，已经在某个通道里的人，不能移动到另一个通道。

初始状态：左通道 $1$ 人，右通道 $1$ 人。

你的任务是：求出最终能得到的最大总人数。

输入格式

第一行一个整数 $t$（$1 \le t \le 10^4$），表示测试用例数。

每组数据：

• 第一行一个整数 $n$（$1 \le n \le 30$），表示门的对数。
• 接下来 $n$ 行，每行描述一对门：先左门，后右门。
• 门的格式为：
  • $+ \ a$（$1 \le a \le 1000$）
  • $\times \ a$（$2 \le a \le 3$）

输出格式

对于每组测试用例，输出一个整数，表示最终的最大总人数。

样例输入

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$，右门 $\times2$。 新增 $4+1=5$ 人，分配 $2$ 人去左，$3$ 人去右。 得到：$l=3,\ r=4$。

• 第二对门：左门 $\times3$，右门 $\times3$。 新增 $6+8=14$ 人，均分。 得到：$l=10,\ r=11$。

• 第三对门：左门 $+7$，右门 $+4$。 新增 $11$ 人，分配后得到：$l=16,\ r=16$。

最终总人数：$16+16=32$。