CF1666B.Budget Distribution

Distributing budgeted money with limited resources and many constraints is a hard problem. A budget plan consists of $t$ topics; $i$-th topic consists of $n_i$ items. For each topic, the optimal relative money distribution is known. The optimal relative distribution for the topic $i$ is a list of real numbers $p_{i,j}$, where $\sum\limits_{j=1}^{n_i}{p_{i,j}} = 1$.

Let's denote the amount of money assigned to $j$-th item of the topic $i$ as $c_{i, j}$; the total amount of money for the topic is $C_i = \sum\limits_{j=1}^{n_i}{c_{i,j}}$. A non-optimality of the plan for the topic $i$ is defined as $\sum\limits_{j=1}^{n_i}\left|\frac{c_{i, j}}{C_i} - p_{i, j}\right|$. Informally, the non-optimality is the total difference between the optimal and the actual ratios of money assigned to all the items in the topic. The total plan non-optimality is the sum of non-optimalities of all $t$ topics. Your task is to minimize the total plan non-optimality.

However, the exact amount of money available is not known yet. $j$-th item of $i$-th topic already has $\hat c_{i,j}$ dollars assigned to it and they cannot be taken back. Also, there are $q$ possible values of the extra unassigned amounts of money available $x_k$. For each of them, you need to calculate the minimal possible total non-optimality among all ways to distribute this extra money. You don't need to assign an integer amount of money to an item, any real number is possible, but all the extra money must be distributed among all the items in addition to $\hat c_{i,j}$ already assigned. Formally, for each value of extra money $x_k$ you'll need to find its distribution $d_{i,j}$ such that $d_{i, j} \ge 0$ and $\sum\limits_{i=1}^{t}\sum\limits_{j=1}^{n_i} d_{i,j} = x_k$, giving the resulting budget assignments $c_{i,j} = \hat c_{i,j} + d_{i,j}$ that minimize the total plan non-optimality.

在资源有限且约束众多的情况下，合理分配预算资金是一项困难的任务。一个预算计划包含 $t$ 个主题；第 $i$ 个主题包含 $n_i$ 个项目。对于每个主题，其最优的相对资金分配比例已知。主题 $i$ 的最优相对分配是一组实数 $p_{i,j}$，满足 $\sum\limits_{j=1}^{n_i}{p_{i,j}} = 1$。

记分配给主题 $i$ 中第 $j$ 个项目的资金金额为 $c_{i, j}$；该主题的总资金为 $C_i = \sum\limits_{j=1}^{n_i}{c_{i,j}}$。主题 $i$ 的非最优性定义为 $\sum\limits_{j=1}^{n_i}\left|\frac{c_{i, j}}{C_i} - p_{i, j}\right|$。直观上，该值表示该主题中所有项目实际资金占比与最优资金占比之间的总绝对偏差。整个预算计划的总非最优性即为所有 $t$ 个主题的非最优性之和。你的任务是使总非最优性最小化。

然而，当前尚不清楚可用资金的确切总额。第 $i$ 个主题中的第 $j$ 个项目目前已预先分配了 $\hat c_{i,j}$ 美元，且这部分资金不可收回。此外，尚有 $q$ 种可能的额外未分配资金数额 $x_k$。对每一个 $x_k$，你需要计算在将该额外资金以任意方式分配后所能达到的最小总非最优性。你无需将整数金额分配给项目（允许分配任意实数），但所有额外资金必须全部分配至各项目，即在已有 $\hat c_{i,j}$ 的基础上额外增加 $d_{i,j}$。形式化地，对每个额外资金量 $x_k$，需找出一组分配量 $d_{i,j}$，满足 $d_{i, j} \ge 0$ 且 $\sum\limits_{i=1}^{t}\sum\limits_{j=1}^{n_i} d_{i,j} = x_k$，使得最终预算分配 $c_{i,j} = \hat c_{i,j} + d_{i,j}$ 所对应的总计划非最优性最小。

The first line contains two integers $t$ ($1 \le t \le 5 \cdot 10^4$) and $q$ ($1 \le q \le 3 \cdot 10^5$) — the number of topics in the budget and the number of possible amounts of extra money.

The next $t$ lines contain descriptions of topics. Each line starts with an integer $n_i$ ($2 \le n_i \le 5$) — the number of items in $i$-th topic; it is followed by $n_i$ integers $\hat c_{i, j}$ ($0 \le \hat c_{i, j} \le 10^5$; for any $i$, at least one of $\hat c_{i,j} \gt 0$) — the amount of money already assigned to $j$-th item in $i$-th topic; they are followed by $n_i$ integers $p'_{i,j}$ ($1 \le p'_{i,j} \le 1000$) — they determine the values of $p_{i,j}$ as $p_{i, j} = {p'_{i, j}} \big/ {\sum\limits_{j=1}^{n_i}{p'_{i, j}}}$ with $\sum\limits_{j=1}^{n_i}{p_{i,j}} = 1$.

The next line contains $q$ integers $x_k$ ($0 \le x_k \le 10^{12}$) — $k$-th possible amount of extra money.

第一行包含两个整数 $t$（$1 \le t \le 5 \cdot 10^4$）和 $q$（$1 \le q \le 3 \cdot 10^5$）——分别表示预算中主题的数量以及可能的额外资金数额的个数。

接下来的 $t$ 行描述各个主题。每行以一个整数 $n_i$（$2 \le n_i \le 5$）开头，表示第 $i$ 个主题中所含项目的数量；随后是 $n_i$ 个整数 $\hat c_{i, j}$（$0 \le \hat c_{i, j} \le 10^5$；对任意 $i$，至少存在一个 $j$ 满足 $\hat c_{i,j} > 0$），表示已分配给第 $i$ 个主题中第 $j$ 个项目的资金数额；再之后是 $n_i$ 个整数 $p'_{i,j}$（$1 \le p'_{i,j} \le 1000$），它们用于确定概率值 $p_{i,j}$，具体定义为 $p_{i, j} = {p'_{i, j}} \big/ {\sum\limits_{j=1}^{n_i}{p'_{i, j}}}$，其中满足 $\sum\limits_{j=1}^{n_i}{p_{i,j}} = 1$。

下一行包含 $q$ 个整数 $x_k$（$0 \le x_k \le 10^{12}$）——第 $k$ 个可能的额外资金数额。

Output $q$ real numbers — the minimal possible non-optimality for the corresponding amount of extra money $x_k$. An absolute or a relative error of the answer must not exceed $10^{-6}$.

输出 $q$ 个实数——对应于额外资金量 $x_k$ 的最小可能非最优性。答案的绝对误差或相对误差不得超过 $10^{-6}$。