ある売り手が $n$ 個のアイテムを1人の買い手に販売しようとしている。買い手は評価プロファイル $\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$ を1つ購入する。もしどのアイテムを購入しても効用が負になる場合は、何も購入しない。もし最大効用を与えるアイテムが複数存在する場合、彼女は価格が最小のものを選択する。売り手の収益は、買い手が購入したアイテムの価格として定義され、買い手が何も購入しない場合の収益は 0 である。

今、評価プロファイル $\bar{v}$ は、$\bar{v}$ のあらゆる可能な値の確率を定義する同時分布 $F$ から抽出されることが分かっている。残念ながら、$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$ が与えられたとき、すべての可能な同時分布の中で最小の期待収益を計算せよ。形式的には、個々のアイテムの価値に対する周辺分布が $F_1, F_2, \dots, F_n$ であるような評価プロファイル $\bar{v}$ 上の同時分布の集合を $\mathcal{F}$ とする。評価プロファイル $\bar{v}$ が同時分布 $F$ から抽出される場合、価格設定 $\bar{p}$ を設定したときの売り手の期待収益を $\text{Rev}(\bar{p}, F)$ とする。我々は以下を計算する必要がある。

$$\min_{F \in \mathcal{F}} \text{Rev}(\bar{p}, F)$$

入力

1行目には、販売するアイテムの数を示す整数 $n$ ($1 \le n \le 10^5$) が含まれる。

2行目には、$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$ が値 $v_j$ をとる確率が $q_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