SP18521 FBWHEELS - Fortunate Wheels

Kit 参加的是一个名为《幸运转轮》的热门游戏节目。在这个节目中有一个由大写字母组成的秘密单词 $ S $（$ 2 \leq |S| \leq 10^5 $），只有主持人知道。参赛者可以通过消耗点数购买字母序列，希望与 $ S $ 的一部分匹配来赚取更多的点数。显然，赚取的点数超过花费的概率非常低，整个节目就像一个骗局。幸好，Kit 已经做好了准备——他竟然知道这个秘密单词！即便如此，要想尽量多得分也并不简单。 节目中有 $ N $（$ 1 \leq N \leq 20 $）种基础交易供参赛者选择。第 $ i $ 种交易需要支付 $ A_i $ 点数（$ 1 \leq A_i \leq 10^4 $），可以选购长度为 $ B_i $ 的任意字母序列（$ 1 \leq B_i < |S| $）。此外，参赛者可以将这些交易进行组合，形成更长的序列。将一个花费为 $ C_1 $、长度为 $ L_1 $ 的交易与另一个花费为 $ C_2 $、长度为 $ L_2 $ 的交易（包括可能是同一个）组合，能产生一个新交易：其花费为 $ C_1 + C_2 + W $（$ 0 \leq W \leq 10^4 $），长度为 $ L_1 + L_2 $（前提是 $ L_1 + L_2 < |S| $）。比如，如果 $ W = 0 $，一个成本和长度都为 1 的基本交易可以反复组合自身，得出任意小于 $ |S| $ 的整数长度的新交易。 Kit 购买的字母序列将会与秘密单词 $ S $ 进行两次匹配。首次匹配时，主持人会随机选择 $ S $ 中的起始位置，以便该序列能完全缩在 $ S $ 内。第二次匹配时，主持人会再次随机选择一个新的起始位置，同样确保序列能完全缩在 $ S $ 内且不重复第一次的结果。比如，如果序列只有一个字母，第一个幸运轮可能会随机选中 $ S $ 中的任一位置，概率为 $ \frac{1}{|S|} $，然后第二个可能会选中剩下的位置之一，概率为 $ \frac{1}{|S|-1} $。但若序列长度为 $ |S|-1 $，第一个幸运轮可能选 0 或 1，第二个则必须选择另一个位置。若两次匹配中，序列均与 $ S $ 的相应子串完全相同，Kit 将获得 $ Y (|S| - |X - \ell|)^2 + Z $ 点数（$ 1 \leq X < |S| $，$ 0 \leq Y, Z \leq 10^9 $），其中 $ \ell $ 为序列长度。如果有任意一个字母不匹配，Kit 则一无所获！看来，游戏行业真不太靠谱。 Kit 认真考虑自己的首次回合。他想尽量多赚点，但又担心选得太好会引起怀疑。因此，他希望找到 $ M $（$ 1 \leq M \leq 20 $）个收益最高的不同行动的期望值，再做决定。两个行动算作不同的，如果它们购买的字母序列不同，哪怕使用的交易相同也不算重。注意，因交易成本的不同，行动的期望值可能会是负数。

第 1 行：1 个整数 $ T $（$ 1 \leq T \leq 150 $），表示测试用例的数量 **针对每个测试用例：** 第 1 行：6 个整数，分别为 $ N $、$ M $、$ W $、$ X $、$ Y $ 和 $ Z $ 第 2 行：1 个字符串，$ S $ 接下来的 $ N $ 行：每行两个整数 $ A_i $ 和 $ B_i $，代表第 $ i $ 个交易的成本和长度

**针对每个测试用例：** 输出 1 行，包含 $ M $ 个实数（精确到小数点后不超过 $ 10^{-2} $），表示可以获得的 $ M $ 个最高期望点数，按降序排列。 **本翻译由 AI 自动生成**