有一个卖家有 $n$ 件商品要卖给一个买家。买家有一个估值向量 $\bar{v} = (v_1, \dots, v_n)$，其中 $v_j \ge 0$ 表示她对第 $j$ 件商品的估值。

卖家可以设定一个定价向量 $\bar{p} = (p_1, \dots, p_n)$。给定定价 $\bar{p}$，购买第 $j$ 件商品的效用为 $v_j - p_j$。买家会购买使效用最大化的那一件商品 $j$，如果购买任何商品的效用都为负，则什么都不买。如果有多件商品具有相同的最大效用，她会选择价格最低的那一件。卖家的收益定义为买家所购商品的价格；如果买家什么都不买，收益为 0。

现在已知估值向量 $\bar{v}$ 服从某个联合分布 $F$，该分布定义了 $\bar{v}$ 每个可能取值的概率。遗憾的是，我们不知道 $F$。但我们知道边际分布 $F_1, F_2, \dots, F_n$：分布 $F_i$ 定义了对于每个可能的 $x$，$v_i = x$ 的概率。但我们不知道它们是如何相关的：这些值不一定是独立的，因此 $v_i = x$ 和 $v_j = y$ 的个体概率并不能定义两者同时发生的概率。注意，联合分布 $F$ 是关于估值向量 $\bar{v}$ 的，而边际分布 $F_i$ 是关于第 $i$ 件商品的价值 $v_i$ 的。

给定定价 $\bar{p}$ 和边际分布 $F_1, F_2, \dots, F_n$，我们现在需要计算在所有可能的联合分布中，最小的期望收益。形式上，令 $\mathcal{F}$ 为所有估值向量 $\bar{v}$ 的联合分布集合，且这些分布对于单个商品价值的边际分布恰好为 $F_1, F_2, \dots, F_n$。令 $\text{Rev}(\bar{p}, F)$ 为当估值向量 $\bar{v}$ 服从联合分布 $F$ 时，卖家设定定价 $\bar{p}$ 后的期望收益。我们需要计算： $$\min_{F \in \mathcal{F}} \text{Rev}(\bar{p}, F)$$

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 10^5$)，表示待售商品的数量。

第二行包含 $n$ 个非负整数 $p_1, p_2, \dots, p_n$ ($0 \le p_i \le 10^5$)，表示定价向量 $\bar{p}$。

接下来的 $n$ 行描述边际分布 $F_1, F_2, \dots, F_n$。每行以一个整数 $k$ 开头：表示 $F_i$ 的支撑集大小（不同值的数量）。随后是 $k$ 对数字 $q_j$ 和 $v_j$ ($0 \le q_j \le 1, 0 \le v_j \le 10^6$)，表示 $F_i$ 以概率 $q_j$ 取值为 $v_j$。值 $v_j$ 可能以小数或科学计数法给出。保证 $\sum_{j=1}^k q_j = 1$。

这 $n$ 行中 $k$ 的总和不超过 $3 \cdot 10^5$。输入总大小不超过 5 兆字节。

输出格式

输出一个实数：所有可能联合分布中的最小期望收益。如果你的答案与标准答案的绝对误差或相对误差不超过 $10^{-6}$，则视为正确。

样例

输入 1

2
2 5
4 0.254 5 0.227 8 0.269 10 0.25 9
4 0.274 9 0.272 9 0.223 8 0.231 7

输出 1

2.0000000000

输入 2

2
7 7
2 0.5 1 0.5 0
2 0.3 5 0.7 1

输出 2

0.0000000000

输入 3

1
5
1 1.0 5

输出 3

5.0000000000