Description

Konstantin 和 Ilia 住在同一栋房子里。Konstantin 住在楼上，喜欢跳跃、搬动家具等一切会制造噪音的活动。Ilia 住在楼下，喜欢睡觉。

为了度过一个愉快的夜晚，Konstantin 希望至少做 $K$ 项活动。昨晚，Ilia 请 Konstantin 尽量不要吵醒他；而 Konstantin 是个非常友善的邻居，他答应了。可惜，他把 Ilia 的请求理解得太过字面，于是他会以最小化 Ilia 被吵醒概率的方式来选择自己的活动顺序。

Konstantin 可以选择的每项活动都有一个相关概率 $a_i / b_i$。如果 Konstantin 执行了这项活动，那么在活动结束时，Ilia 会以 $a_i / b_i$ 的概率是清醒的，否则是睡着的——无论活动前 Ilia 是什么状态。此外，每项活动至多可以执行 $c_i$ 次（超过这个次数会觉得无聊，而无聊的夜晚可不是好夜晚）。

Konstantin 希望选择一系列活动，按顺序进行，使得：

• 总共进行的活动数不少于 $K$；
• 第 $i$ 项活动最多执行 $c_i$ 次；
• Ilia 在活动过程中被吵醒一次或多次的概率 $Q$ 尽可能小。

Ilia 初始是清醒的，因此，只有在某项活动结束时 Ilia 处于睡着状态，且紧接着下一项活动结束时 Ilia 变为清醒，才算作 Ilia 被吵醒了一次。

Konstantin 无法判断 Ilia 当前是清醒还是睡着，因此他不能根据 Ilia 的状态调整自己的活动选择。

问 Konstantin 在度过一个愉快夜晚的前提下，最小能做到的 $Q$ 是多少？注意：Konstantin 无法得知 Ilia 的状态，因此不能根据状态自适应选择活动。

Input Format

输入的第一行为测试用例数 $T$。接下来有 $T$ 组测试数据。每组测试数据首先一行两个整数 $N$、$K$。接下来 $N$ 行，每行描述一种活动，格式为 "$a_i/b_i$ $c_i$"，表示该活动结束时 Ilia 以 $a_i/b_i$ 的概率清醒，且该活动最多可执行 $c_i$ 次。

Output Format

对于每个测试用例，输出一行 "Case #$x$: $Q$"，其中 $x$ 为测试用例编号（从 1 开始），$Q$ 为 Konstantin 执行这些活动过程中 Ilia 被吵醒的最小概率。答案的绝对或相对误差不超过 $10^{-6}$ 即视为正确。

3
4 1
1/2 3
1/5 2
2/5 1
2/2 2
3 2
1/2 2
1/3 2
3/4 2
3 3
99/100 1
1/2 2
1/50 3

Case #1: 0.000000000
Case #2: 0.083333333
Case #3: 0.015000000

Hint

限制条件

• $1 \leq T \leq 100$
• 对所有 $i$，$0 \leq a_i \leq b_i \leq 1000000$
• 对所有 $i$，$1 \leq b_i$ 且 $1 \leq c_i$
• $1 \leq K \leq$ 本组测试数据所有 $c_i$ 之和

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

• 时间限制：30 6 秒
• $1 \leq N \leq 100$
• 本组测试数据所有 $c_i$ 之和不超过 $100$

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

• 时间限制：60 12 秒
• $1 \leq N \leq 10000$
• 本组测试数据所有 $c_i$ 之和不超过 $10^6$

翻译由 ChatGPT-4.1 完成。