Considérez un tableau $A$ de longueur $N$. Vous prévoyez d'effectuer plusieurs requêtes : pour un segment $[i, j]$ du tableau, trouvez la valeur maximale sur ce segment du tableau. La requête pour les indices $i$ et $j$ sera effectuée $Q_{i,j}$ fois.

Cependant, le tableau n'est pas donné, et vous allez le construire dès maintenant.

Pour chaque $i$ allant de $1$ à $N$, vous pouvez choisir l'une des $K_i$ valeurs différentes $V_{i,j}$ comme valeur de $A_i$, et les coûts respectifs pour choisir ces valeurs sont $C_{i,j}$.

Après toutes les requêtes, votre score sera la somme des résultats de toutes les requêtes d'intervalle que vous prévoyez d'effectuer, moins le coût du choix des valeurs $A_i$. Trouvez le score maximum possible pouvant être atteint.

Entrée

La première ligne de l'entrée contient un entier $N$ ($1 \le N \le 300$).

Ensuite, $N$ lignes suivent. La $i$-ième de ces lignes contient des entiers de $Q_{i,i}$ à $Q_{i,N}$ ($0 \le Q_{i,j} \le 999$). La requête pour l'élément maximum dans le tableau entre $A_i$ et $A_j$ inclus doit être effectuée exactement $Q_{i,j}$ fois.

Après cela, l'entrée décrit les valeurs possibles de $A_i$ pour chaque $i$ de $1$ à $N$. La $i$-ième description a le format suivant :

• La première ligne contient un entier positif $K_i$ : le nombre de valeurs possibles pour $A_i$.
• Chacune des $K_i$ lignes suivantes contient deux entiers $V_{i,j}$ et $C_{i,j}$ : une valeur possible et le coût de sélection de cette valeur, respectivement ($0 \le V_{i,j} \le 10^8$, $0 \le C_{i,j} \le 10^{13}$).

Il est garanti que la somme des $K_i$ est au plus $3 \cdot 10^5$.

Sortie

Affichez un entier : le score maximum possible.

Exemples

Entrée 1

5
1 0 2 2 0
0 2 2 0
2 2 2
1 2
0
2
0 27
1 19
2
7 25
1 1
2
8 7
4 18
2
8 7
4 4
2
0 25
4 26

Sortie 1

78

Entrée 2

2
1 1
1
2
1 100
2 50
1
1 100

Sortie 2

-145