Un vendeur propose $n$ articles à un acheteur unique. L'acheteur possède un profil de valorisation $\bar{v} = (v_1, \dots, v_n)$, où $v_j \ge 0$ désigne sa valeur pour l'article $j$.

Le vendeur peut fixer une tarification $\bar{p}$, c'est-à-dire un vecteur de prix des articles $(p_1, \dots, p_n)$. Étant donné une tarification $\bar{p}$, l'utilité de l'achat de l'article $j$ est $v_j - p_j$. L'acheteur achètera l'article unique $j$ qui maximise son utilité, ou rien si son utilité pour l'achat de n'importe quel article est négative. S'il existe plusieurs articles offrant la même utilité maximale, elle choisira celui dont le prix est minimal. Le revenu du vendeur est défini comme le prix de l'article acheté par l'acheteur, et si l'acheteur n'achète rien, le revenu est de $0$.

Nous savons maintenant que le profil de valorisation $\bar{v}$ est tiré d'une distribution jointe $F$ qui définit la probabilité de chaque valeur possible de $\bar{v}$. Malheureusement, nous ne connaissons pas $F$. Au lieu de cela, nous connaissons les distributions marginales $F_1, F_2, \dots, F_n$ : la distribution $F_i$ définit la probabilité que $v_i = x$ pour chaque $x$ possible. Mais nous ne savons pas comment elles sont corrélées : les valeurs ne sont pas nécessairement indépendantes, donc les probabilités individuelles que $v_i = x$ et $v_j = y$ ne définissent pas la probabilité que les deux se produisent simultanément. Notez que la distribution jointe $F$ porte sur le profil de valorisation $\bar{v}$ et que la distribution marginale $F_i$ porte sur la valeur $v_i$ de l'article $i$.

Étant donné la tarification $\bar{p}$ et les distributions marginales $F_1, F_2, \dots, F_n$, nous devons calculer le revenu espéré minimal parmi toutes les distributions jointes possibles. Formellement, soit $\mathcal{F}$ l'ensemble des distributions jointes sur les profils de valorisation $\bar{v}$ dont les distributions marginales pour les valeurs individuelles des articles sont exactement $F_1, F_2, \dots, F_n$. Soit $\text{Rev}(\bar{p}, F)$ le revenu espéré du vendeur en fixant une tarification $\bar{p}$, si le profil de valorisation $\bar{v}$ est tiré d'une distribution jointe $F$. Nous devons calculer :

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

Entrée

La première ligne contient un entier unique $n$ ($1 \le n \le 10^5$), le nombre d'articles à vendre.

La deuxième ligne contient $n$ entiers non négatifs $p_1, p_2, \dots, p_n$ ($0 \le p_i \le 10^5$), le vecteur de tarification $\bar{p}$.

Les $n$ lignes suivantes décrivent les distributions marginales $F_1, F_2, \dots, F_n$. Chaque ligne commence par un entier $k$ : la taille du support (nombre de valeurs différentes) de $F_i$. Suivent ensuite $k$ paires de nombres $q_j$ et $v_j$ ($0 \le q_j \le 1$, $0 \le v_j \le 10^6$), signifiant que $F_i$ a une probabilité $q_j$ d'avoir la valeur $v_j$. Les valeurs $v_j$ peuvent être données sous forme de fractions décimales ou en notation scientifique. Il est garanti que $\sum_{j=1}^k q_j = 1$.

La somme totale des valeurs de $k$ sur ces $n$ lignes ne dépassera pas $3 \cdot 10^5$. La taille totale de l'entrée ne dépassera pas 5 mébioctets.

Sortie

Affichez un nombre réel unique : le revenu espéré minimal parmi toutes les distributions jointes possibles. Votre réponse sera considérée comme correcte si et seulement si son erreur absolue ou relative n'excède pas $10^{-6}$.

Exemples

Entrée 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

Sortie 1

2.0000000000

Entrée 2

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

Sortie 2

0.0000000000

Entrée 3

1
5
1 1.0 5

Sortie 3

5.0000000000