CF2078D.Scammy Game Ad

考虑以下游戏。

游戏中每个关卡包含 $n$ 对门。每对门包含一个左门和一个右门。每个门执行以下两种操作之一：

• 加法操作 (+ $a$)：将该通道的人数增加固定值 $a$。
• 乘法操作 (× $a$)：将该通道当前人数乘以整数 $a$。这意味着该通道人数将增加 $(a - 1)$ 倍当前值。

每个操作产生的新增人员可以分配到任意通道。但已存在于某个通道的人员不可转移到另一个通道。

初始时，每个通道各有 $1$ 人。你的任务是确定关卡结束时可达到的最大总人数。

第一行输入整数 $t$（$1 \leq t \leq 10^4$）——测试用例数量。

每个测试用例的第一行包含一个整数 $n$（$1 \leq n \le 30$）——门对的数量。

接下来每个测试用例的 $n$ 行依次描述每对门的左门和右门信息。每个门的信息以 + $a$（$1 \le a \le 1000$）或 × $a$（$2 \le a \le 3$）形式给出，其中 $a$ 为整数。

对于每个测试用例，输出一个整数——关卡结束时的最大总人数。

第一个测试用例的最优操作方式如下：

初始时，左通道人数 $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$ 人到两个通道
• 结果：$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$。

翻译由 DeepSeek R1 完成