수익

판매자가 한 명의 구매자에게 팔 상품 $n$ 개를 가지고 있다. 구매자는 가치 프로필 $\bar{v} = (v_1, \ldots, v_n)$을 가지며, $v_j \ge 0$은 상품 $j$에 대한 구매자의 가치이다.

판매자는 가격 책정 $\bar{p}$, 즉 상품 가격 벡터 $(p_1, \ldots, p_n)$을 정한다. $\bar{p}$가 주어지면 상품 $j$를 구매했을 때의 효용은 $v_j - p_j$이다. 구매자는 효용을 최대로 하는 상품 $j$ 하나를 산다. 모든 효용이 음수이면 아무것도 사지 않는다. 최대 효용을 갖는 상품이 여럿이면 가격이 가장 낮은 상품을 고른다. 수익은 구매자가 산 상품의 가격이며, 아무것도 사지 않으면 0이다.

가치 프로필 $\bar{v}$는 가능한 모든 프로필 위에 정의된 알려지지 않은 결합 분포 $F$에서 뽑힌다. 판매자가 아는 것은 주변 분포 $F_1, \ldots, F_n$뿐이며, $F_i$는 각 값 $v_i = x$의 확률을 준다. 값들은 서로 상관될 수 있으므로, $v_i = x$와 $v_j = y$가 동시에 성립할 확률은 $F_i$와 $F_j$만으로 정해지지 않는다. $F$는 가치 프로필 $\bar{v}$ 전체에 대한 분포이고, $F_i$는 단일 값 $v_i$에 대한 분포라는 점에 유의하라.

$\bar{p}$와 주변 분포가 주어졌을 때, 주변 분포가 $F_1, \ldots, F_n$인 모든 결합 분포 중 기대 수익의 최솟값을 구하라. $\mathrm{Rev}(\bar{p}, F)$를 분포 $F$ 아래의 기대 수익이라 하자. 그 주변 분포를 갖는 결합 분포의 집합을 $\mathcal{F}$라 할 때, $\min_{F \in \mathcal{F}} \mathrm{Rev}(\bar{p}, F)$를 계산하라.

첫째 줄에 상품의 개수 $n$ ($1 \le n \le 10^5$)이 주어진다.

둘째 줄에는 가격 벡터 $p_1, \ldots, p_n$ ($0 \le p_i \le 10^5$)을 나타내는 음이 아닌 정수 $n$ 개가 주어진다.

다음 $n$ 줄은 각각 $F_i$를 나타낸다. 각 줄은 $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} q_j = 1$이 보장된다.

모든 줄의 $k$ 합은 $3 \cdot 10^5$을 넘지 않는다. 입력 크기는 5 MiB를 넘지 않는다.

최소 기대 수익을 나타내는 실수 하나를 출력하라. 절대 오차 또는 상대 오차가 $10^{-6}$ 이하이면 정답으로 인정한다.