有一位賣家有 $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{p}$ 後，若估價檔案 $\bar{v}$ 是從聯合分佈 $F$ 中抽取時的預期營收。我們被要求計算： $$\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 mebibytes。

輸出格式

輸出一個實數：所有可能聯合分佈中的最小預期營收。若你的答案的絕對誤差或相對誤差不超過 $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

2.0000000000

範例 2

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

0.0000000000

範例 3

1
5
1 1.0 5

5.0000000000