P13333 [GCJ 2012 Finals] Upstairs/Downstairs

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 的状态，因此不能根据状态自适应选择活动。

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

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

**限制条件** - $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 完成。