在资源有限且受到诸多限制的情况下分配预算资金是一个难题。一个 预算计划 由 $$$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}}$$$。一个 非最优 定义为 $$$\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$$$。对于每种方法,您都需要计算分配这笔额外资金的所有方法中可能的最小总非最优性。您不需要为某个项目分配整数金额,任何实数都可以,但除了已分配的 $$$\hat c_{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}$$$ 最小化总计划非最优性。
输入
第一行包含两个整数 $$$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$$$,至少 $$$\hat c_{i,j} \gt 0$$$ 之一) — 已分配给 $$$j$$$ 中第 $$$j$$$ 项的金额第 $$$i$$$ 个主题;它们后面跟着 $$$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$$$ - 第可能的额外金额。
输出
输出 $$$q$$$ 实数 - 相应金额的额外资金 $$$x_k$$$ 的最小可能非最优值。答案的绝对或相对误差不得超过$$$10^{-6}$$$。
示例
输入复制
1 5 3 1 7 10 700 400 100 0 2 10 50 102
输出复制
1.0555555555555556 0.8666666666666667 0.5476190476190478 0.12745098039215708 0.0
输入复制
2 5 3 10 70 100 700 400 100 3 10 30 100 700 400 100 2 10 50 70 110
输出复制
2.2967032967032974 2.216776340655188 1.8690167362600323 1.7301587301587305 1.5271317829457367