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 完成