Rozważmy tablicę $A$ o długości $N$. Planujesz wykonać kilka zapytań: dla przedziału $[i, j]$ tablicy znajdź wartość maksymalną na tym przedziale. Zapytanie dla indeksów $i$ oraz $j$ zostanie wykonane $Q_{i,j}$ razy.

Tablica nie jest jednak podana i musisz ją teraz zbudować.

Dla każdego $i$ od $1$ do $N$ możesz wybrać jedną z $K_i$ różnych wartości $V_{i,j}$ jako wartość $A_i$, przy czym odpowiednie koszty wyboru tych wartości wynoszą $C_{i,j}$.

Po wykonaniu wszystkich zapytań, Twój wynik będzie sumą rezultatów wszystkich zaplanowanych zapytań przedziałowych minus koszt wyboru wartości $A_i$. Znajdź maksymalny możliwy do uzyskania wynik.

Wejście

Pierwsza linia wejścia zawiera jedną liczbę całkowitą $N$ ($1 \le N \le 300$).

Następnie następuje $N$ linii. $i$-ta z tych linii zawiera liczby całkowite od $Q_{i,i}$ do $Q_{i,N}$ ($0 \le Q_{i,j} \le 999$). Zapytanie o element maksymalny w tablicy pomiędzy $A_i$ oraz $A_j$ włącznie zostanie wykonane dokładnie $Q_{i,j}$ razy.

Następnie wejście opisuje możliwe wartości $A_i$ dla każdego $i$ od $1$ do $N$. $i$-ty opis ma następujący format:

• Pierwsza linia zawiera liczbę całkowitą dodatnią $K_i$: liczbę możliwych wartości dla $A_i$.
• Każda z kolejnych $K_i$ linii zawiera dwie liczby całkowite $V_{i,j}$ oraz $C_{i,j}$: odpowiednio możliwą wartość oraz koszt jej wybrania ($0 \le V_{i,j} \le 10^8$, $0 \le C_{i,j} \le 10^{13}$).

Gwarantuje się, że suma $K_i$ wynosi co najwyżej $3 \cdot 10^5$.

Wyjście

Wypisz jedną liczbę całkowitą: maksymalny możliwy wynik.

Przykład

Wejście 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

Wyjście 1

78

Wejście 2

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

Wyjście 2

-145