P13027 [GCJ 2021 #1A] Prime Time

你正在玩一款名为**质数时刻**的新单人纸牌游戏。你有一副卡牌，每张牌上写有一个质数，不同牌可能写有相同的数字。 游戏目标是将所有卡牌分成两组：第一组卡牌上的数字之和等于第二组卡牌上的数字之积。每张牌必须属于其中一组，且每组至少包含一张牌。若某组仅有一张牌，则该组的和或积即为该牌上的数字。  例如上图中，左侧卡牌数字之和为 $25$，右侧卡牌数字之积也为 $25$，因此这是一个有效的分组方案。 你的得分等于第一组数字之和（即第二组数字之积），若无法完成这样的分组则得分为 $0$。你能获得的最高得分是多少？

输入第一行包含测试用例数量 $\mathbf{T}$。随后每个测试用例包含： - 第一行：整数 $\mathbf{M}$，表示牌堆中不同质数的种类数 - 接下来 $\mathbf{M}$ 行：每行两个数 $\mathbf{P}_i$ 和 $\mathbf{N}_i$，表示有 $\mathbf{N}_i$ 张数字为 $\mathbf{P}_i$ 的卡牌 注意牌堆总卡牌数为所有 $\mathbf{N}_i$ 之和。

对每个测试用例，输出 `Case #x: y`，其中 $x$ 为测试用例编号（从 1 开始），$y$ 为可获得的最大得分。

**样例解释** 在样例 #1 中，最优分组为 $11 + 2 + 7 + 3 + 2 = 5 \cdot 5$。另一可行分组 $5 + 7 + 3 + 2 + 5 = 11 \cdot 2$ 得分较低。 在样例 #2 中，注意相同数字的卡牌可以分到不同组。 **数据范围** - $1 \leq \mathbf{T} \leq 100$ - $1 \leq \mathbf{M} \leq 95$（在 2 至 499 之间的质数共 95 个） - $2 \leq \mathbf{P}_i \leq 499$（均为质数） - $\mathbf{P}_i < \mathbf{P}_{i+1}$（质数按严格递增顺序给出） - $1 \leq \mathbf{N}_i$ **测试集 1（7 分，可见判定）** - 总卡牌数 $2 \leq \sum \mathbf{N}_i \leq 10$ **测试集 2（13 分，可见判定）** - 总卡牌数 $2 \leq \sum \mathbf{N}_i \leq 100$ **测试集 3（15 分，隐藏判定）** - 总卡牌数 $2 \leq \sum \mathbf{N}_i \leq 10^{15}$ 翻译由 DeepSeek V3 完成