多台轮盘

题目描述

有 $N$ 台轮盘。 第 $i$ 台（$1 \le i \le N$）轮盘上写着 $P_i$ 个整数 $S_{i, 1}, S_{i, 2}, \ldots, S_{i, P_i}$，支付 $C_i$ 日元即可玩一次。 当你玩一次第 $i$ 台轮盘时，会从 $1$ 到 $P_i$（含）中均匀随机选择一个整数 $j$，并获得 $S_{i, j}$ 分。

各次玩轮盘获得的分数相互独立，与之前的结果无关。

高桥君想获得至少 $M$ 分。 高桥君会采取行动，使自己在获得至少 $M$ 分之前支付的金额尽可能少。 每次玩完后，他可以根据之前的结果选择下一次玩哪台轮盘。

求高桥君在获得至少 $M$ 分之前所支付金额的期望值。

更正式的定义如下。

对于高桥君在选择轮盘时可能采取的一种策略，定义该策略下他在获得至少 $M$ 分之前支付金额的期望值 $E$ 如下：

对于自然数 $X$，设 $f(X)$ 为在该策略下，高桥君在获得至少 $M$ 分或总共玩了 $X$ 次轮盘之前所支付金额的期望值。令 $E = \lim_{X \to +\infty} f(X)$。

在本问题的条件下，可以证明无论高桥君采取何种策略，$\lim_{X \to +\infty} f(X)$ 都是有限的。 求他采取使 $E$ 最小的策略时 $E$ 的值。

输入格式

输入按以下格式从标准输入给出：

$N$ $M$
$C_1$ $P_1$ $S_{1, 1}$ $S_{1, 2}$ $\ldots$ $S_{1, P_1}$
$C_2$ $P_2$ $S_{2, 1}$ $S_{2, 2}$ $\ldots$ $S_{2, P_2}$
$\vdots$
$C_N$ $P_N$ $S_{N, 1}$ $S_{N, 2}$ $\ldots$ $S_{N, P_N}$

输出格式

在一行内输出高桥君在获得至少 $M$ 分之前所支付金额的期望值。 当输出与真实值的相对误差或绝对误差不超过 $10^{-5}$ 时判为正确。

样例

3 14
100 2 5 9
50 4 1 2 4 8
70 5 2 4 2 8 8

215.913355350494384765625

例如，高桥君可以这样玩：

• 支付 $50$ 日元玩轮盘 2，获得 $S_{2, 4} = 8$ 分。
• 支付 $50$ 日元玩轮盘 2，获得 $S_{2, 1} = 1$ 分。
• 支付 $100$ 日元玩轮盘 1，获得 $S_{1, 1} = 5$ 分。此时他已累计获得 $8 + 1 + 5 \ge 14$ 分，于是停止游戏。

此时，他在获得 14 分之前支付了 200 日元。

当输出与真实值的相对误差或绝对误差不超过 $10^{-5}$ 时判为正确，因此输出 215.9112 或 215.9155 也会被判为正确。

2 100
1 2 1 2
10 6 0 0 0 0 0 100

60

一直转动轮盘 2 直到获得 100 分是最优的。

20 90
3252 9 0 4 2 7 3 2 3 2 4
2147 1 1
4033 8 0 4 1 7 5 2 5 0
3795 6 6 6 2 3 2 2
3941 7 2 4 4 7 2 0 5
2815 6 2 1 0 5 2 2
3020 2 3 6
3858 9 4 2 7 3 0 4 4 6 5
4533 10 3 6 4 0 6 4 4 2 7 7
4198 8 6 7 0 6 3 6 5 6
3739 8 2 7 1 5 1 4 4 7
2465 4 1 4 0 1
4418 9 7 6 2 4 6 1 5 0 7
5450 12 0 4 4 7 7 4 4 5 4 5 3 7
4196 9 1 6 5 5 7 2 3 6 3
4776 9 2 2 7 3 6 6 1 6 6
2286 3 3 5 6
3152 3 4 1 5
3509 7 0 6 7 0 1 0 3
2913 6 0 1 5 0 5 6

45037.072314895291126319493887599716

数据范围

• $1 \le N \le 100$
• $1 \le M \le 100$
• $1 \le C_i \le 10^4$（$1 \le i \le N$）
• $1 \le P_i \le 100$（$1 \le i \le N$）
• $0 \le S_{i, j} \le M$（$1 \le i \le N, 1 \le j \le P_i$）
• $\sum_{j=1}^{P_i} S_{i, j} \gt 0$（$1 \le i \le N$）
• 输入均为整数。