Description

在 Code Jam，我们非常喜欢玩一个叫做 Operation 的游戏。（不，这和外科手术没有任何关系；你为什么会这么想呢？）这个游戏是用卡牌来进行的，每张卡牌上都标有一个基本的算术运算（加法、减法、乘法或除法）$\mathbf{O}_i$，以及该运算的右操作数 $\mathbf{V}_i$，它是一个整数。例如，一张卡牌可能写着 $+\ 0$，或者 $-\ -2$，又或者 $/\ -4$ —— 注意，操作数可以是负数，也可以是零，但带有除法操作的卡牌，其操作数绝不会是 $0$。

每一轮游戏会选定一个初始整数值 $\mathbf{S}$，并摆出一组 $\mathbf{C}$ 张卡牌。玩家需要自行决定这些卡牌的出牌顺序，每张卡牌都必须且只能使用一次。之后，这些操作会按照卡牌顺序依次作用在起始值 $\mathbf{S}$ 上，最终得到一个结果。

虽然卡牌上的操作数都是整数，但实际运算是在有理数范围内执行的。例如，假设初始值为 $5$，卡牌分别为 $+\ 1$、$-\ 2$、$*\ 3$ 和 $/\ -2$。如果按照上述顺序出牌，最终结果是 $(5 + 1 - 2) * 3 / (-2) = -6$。注意，所有操作都严格按照卡牌顺序依次执行，不考虑运算符优先级。另一方面，如果你选择的顺序是 $-\ 2$、$/\ -2$、$+\ 1$、$*\ 3$，那么结果就是 $((5 - 2) / (-2) + 1) * 3 = -3 / 2$。这个例子中，这样的顺序实际上可以获得这一组卡牌能得到的最大值。

给定一组卡牌，你能算出通过合理排序后，最终可能得到的最大结果吗？请将答案以最简分数形式输出，分母需为正数。

Input Format

输入的第一行给出测试用例的数量 $\mathbf{T}$。接下来有 $\mathbf{T}$ 组测试用例。每组测试用例的第一行为两个整数 $\mathbf{S}$ 和 $\mathbf{C}$，分别表示游戏的起始值和卡牌数量。接下来的 $\mathbf{C}$ 行，每行描述一张卡牌，包括一个字符 $\mathbf{O}_i$（表示操作类型，可能为 $+$、$-$、$*$ 或 $/$）和一个整数 $\mathbf{V}_i$（表示操作数）。

Output Format

对于每组测试用例，输出一行，内容为 Case #x: y z，其中 $x$ 表示测试用例编号（从 1 开始），$y$ 和 $z$ 是整数，满足 $y/z$ 是该组卡牌能获得的最大最终值，且 $y$ 和 $z$ 互质（除了 $1$ 和 $-1$ 以外没有公约数），并且 $z$ 必须严格大于 $0$。

5
1 2
- 3
* 2
5 4
+ 1
- 2
* 3
/ -2
1000 7
* -1000
* -1000
* 1000
* 1000
* 1000
* 1000
* 1000
-1 3
- -1
* 0
/ -1
0 1
+ 0

Case #1: -1 1
Case #2: -3 2
Case #3: 1000000000000000000000000 1
Case #4: 1 1
Case #5: 0 1

Hint

样例解释

在样例第 1 组中，最优策略是先打出 $*\ 2$ 卡牌，再打 $-\ 3$ 卡牌，最终结果为 $-1$。按题目要求，最简分数表达为 $-1\ 1$。

样例第 2 组对应题面第三段的例子。

样例第 3 组，无论卡牌顺序如何，答案都相同。注意，答案的分子大到无法用 64 位整数表示。

样例第 4 组，最大结果为 $1$。一种可行顺序为：$/\ -1$、$*\ 0$、$-\ -1$。

样例第 5 组，唯一合法的答案为 $0\ 1$。$0\ 2$ 不合法，因为可以约分；$0\ -1$ 也不合法，因为分母必须为正数。

限制条件

• $1 \leq T \leq 100$。
• $-1000 \leq S \leq 1000$。
• 对所有 $i$，$O_i$ 为 $+$、$-$、$*$ 或 $/$。
• 对所有 $i$，$-1000 \leq V_i \leq 1000$。
• 若 $O_i = /$，则 $V_i \neq 0$。

小数据集（10 分，测试集 1 - 可见）

• 时间限制：60 15 秒。
• $1 \leq C \leq 15$。

大数据集（20 分，测试集 2 - 隐藏）

• 时间限制：120 30 秒。
• $1 \leq C \leq 1000$。

翻译由 GPT4.1 完成。