Description

一场考试包含 $\mathbf{Q}$ 道判断题，每道题的正确答案是 $\mathsf{T}$ 或 $\mathsf{F}$。每位考生为每道题选择 $\mathsf{T}$ 或 $\mathsf{F}$，其得分是答对的题数。

已有 $\mathbf{N}$ 名学生参加了这场考试。对于每名学生，你知道他们的答案和最终得分。假设所有与学生得分一致的正确答案序列出现的概率相同，你需要最大化自己的期望得分。请确定该期望得分，并给出能达到该得分的答题方案。

Input Format

输入的第一行包含测试用例的数量 $\mathbf{T}$。随后是 $\mathbf{T}$ 个测试用例。每个测试用例的第一行包含两个整数 $\mathbf{N}$ 和 $\mathbf{Q}$：分别表示学生人数和题目数量。接下来的 $\mathbf{N}$ 行，每行包含一个字符串 $\mathbf{A}_i$ 和一个整数 $\mathbf{S}_i$：分别表示第 $i$ 名学生的答案和得分。$\mathbf{A}_i$ 的第 $j$ 个字符是 $\mathsf{T}$ 或 $\mathsf{F}$，表示第 $i$ 名学生第 $j$ 道题的答案。

Output Format

对于每个测试用例，输出一行 Case #x: y z/w，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是一个字符串，表示能获得最大期望得分的答案序列（格式与输入相同），$\frac{z}{w}$ 是最大期望得分的最简分数形式（即 $w$ 必须为正且最小）。

4
1 3
FFT 3
1 3
FFT 2
2 6
FFTTTF 2
FTFTFT 4
2 2
FF 1
TT 1

Case #1: FFT 3/1
Case #2: FFT 2/1
Case #3: FTFFFT 4/1
Case #4: TF 1/1

1
3 120
FFTFFFTFFFTTTTTTTFTFFFFFFTTTFTFFFTFTFFTTFTFFTFFTTTFTFTFFTFTFTTFFFFTFTFFFFTTTFTTFTTTTFFFTTFFFFFTTFFTFFTFFTTTFFFFTTFFTFTTF 55
FFFTFFTTFFFFTFTFFTFFFTTTTTTFFFTTTFTTTTFFTFTTTFTTFFTTTFTFFFFTFFTTFFTTFTTFFTFTFFTFTTFTFTFFTTTFFTFTFTTFFTFTFTFTTFFTFFFTFTFT 62
FFFTFTTFFFFFTFTFTTTTTTFFTTFTFFFTFFTTTTTTFFFTTTFFFTTFTFFFFFFTFTTFFTFTTTFTTTTFTTFFFFTFFTTFTFFTTTTTTFTFFFFFTTFFTFTFTFFTTTTT 64

Case #1: FFFTFTTTFFFFTFTFFTFTTTTTTTFFFFTTTFTTTTFFTFTTTTTFFFTFTFTFFFFTFFTTFTFTFTTTTTFFTFFFFFFFFTTFTTTTTTFTTTTFFFFTFTFTTFTFFFFTTTFT 189154508532118369075350624633/2901503505434414233388602018

Hint

样例解释

在样例 #1 中，由于 $\mathsf{FFT}$ 的得分为 3，正确答案序列必须是 $\mathsf{FFT}$。

在样例 #2 中，由于 $\mathsf{FFT}$ 的得分为 2，正确答案序列可能是 $\mathsf{FFF}$、$\mathsf{FTT}$ 或 $\mathsf{TFT}$，每种概率为 $\frac{1}{3}$。最佳策略是回答 $\mathsf{FFT}$，期望得分为 $\frac{1}{3} \times 2 + \frac{1}{3} \times 2 + \frac{1}{3} \times 2 = 2$。

在样例 #3 中，其他答案（如 $\mathsf{FTFTFT}$）也能达到期望得分 4。

在样例 #4 中，一道题的答案是 $\mathsf{T}$，另一道是 $\mathsf{F}$，但无法确定顺序。回答 $\mathsf{TF}$ 或 $\mathsf{FT}$ 有 $\frac{1}{2}$ 概率得 2 分，$\frac{1}{2}$ 概率得 0 分，期望得分为 1。回答 $\mathsf{FF}$ 或 $\mathsf{TT}$ 保证得 1 分。由于所有答案序列的期望得分相同，可以输出任意一个。

样例 2 符合测试集 3 的限制。它不会用于测试你的提交。

在测试集 3 的样例中，你可以获得超过 65 的期望得分，高于其他学生的实际得分。注意，期望分数的分子和分母可能远大于 $2^{64}$（此样例的分子实际超过 $2^{97}$）。

数据范围

• $1 \leq \mathbf{T} \leq 2021$。
• 对于所有 $i$，$\mathbf{A}_{\mathbf{i}}$ 的长度为 $\mathbf{Q}$。
• 对于所有 $i$，$\mathbf{A}_{\mathbf{i}}$ 的每个字符是大写 $\mathsf{T}$ 或 $\mathsf{F}$。
• 对于所有 $i$，$0 \leq \mathbf{S}_{\mathbf{i}} \leq \mathbf{Q}$。
• 输入至少存在一个一致的正确答案序列。

测试集 1（8 分，可见评测结果）

• $1 \leq \mathbf{N} \leq 2$。
• $1 \leq \mathbf{Q} \leq 10$。

测试集 2（6 分，隐藏评测结果）

• $1 \leq \mathbf{N} \leq 2$。
• $1 \leq \mathbf{Q} \leq 40$。

测试集 3（25 分，隐藏评测结果）

• $1 \leq \mathbf{N} \leq 3$。
• $1 \leq \mathbf{Q} \leq 120$。

翻译由 DeepSeek V3 完成