판매자가 단일 구매자에게 판매할 $n$개의 아이템을 가지고 있다. 구매자는 아이템 $j$에 대한 가치 $v_j \ge 0$을 나타내는 가치 프로필 $\bar{v} = (v_1, \dots, v_n)$을 가진다.

판매자는 가격 벡터 $\bar{p} = (p_1, \dots, p_n)$을 설정할 수 있다. 가격 $\bar{p}$가 주어졌을 때, 아이템 $j$를 구매함으로써 얻는 효용은 $v_j - p_j$이다. 구매자는 자신의 효용을 최대화하는 단일 아이템 $j$를 구매하거나, 어떤 아이템을 구매해도 효용이 음수라면 아무것도 구매하지 않는다. 만약 최대 효용을 주는 아이템이 여러 개라면, 그중 가격이 가장 낮은 아이템을 선택한다. 판매자의 수익은 구매자가 구매한 아이템의 가격으로 정의되며, 구매자가 아무것도 구매하지 않으면 수익은 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)$$

입력

첫 번째 줄에는 판매할 아이템의 개수인 정수 $n$ ($1 \le n \le 10^5$)이 주어진다.

두 번째 줄에는 가격 벡터 $\bar{p}$를 나타내는 $n$개의 음이 아닌 정수 $p_1, p_2, \dots, p_n$ ($0 \le p_i \le 10^5$)이 주어진다.

다음 $n$개의 줄은 주변 분포 $F_1, F_2, \dots, F_n$을 설명한다. 각 줄은 $F_i$의 지지 집합 크기(서로 다른 값의 개수)인 정수 $k$로 시작한다. 그 뒤를 이어 $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

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