Considera un arreglo $A$ de longitud $N$. Estás planeando realizar varias consultas: para un segmento $[i, j]$ del arreglo, encuentra el valor máximo en ese segmento del arreglo. La consulta para los índices $i$ y $j$ se realizará $Q_{i,j}$ veces.

Sin embargo, el arreglo no está dado y vas a construirlo ahora mismo.

Para cada $i$ desde $1$ hasta $N$, puedes seleccionar uno de $K_i$ valores diferentes $V_{i,j}$ como el valor de $A_i$, y los costos respectivos de elegir estos valores son $C_{i,j}$.

Después de todas las consultas, tu puntuación será la suma de los resultados de todas las consultas de intervalo que planeas realizar, menos el costo de elegir los valores $A_i$. Encuentra la puntuación máxima posible que se puede lograr.

Entrada

La primera línea de la entrada contiene un entero $N$ ($1 \le N \le 300$).

Luego siguen $N$ líneas. La $i$-ésima de esas líneas contiene enteros desde $Q_{i,i}$ hasta $Q_{i,N}$ ($0 \le Q_{i,j} \le 999$). La consulta para el elemento máximo en el arreglo entre $A_i$ y $A_j$ inclusive se realizará exactamente $Q_{i,j}$ veces.

Después de eso, la entrada describe los posibles valores de $A_i$ para cada $i$ desde $1$ hasta $N$. La $i$-ésima descripción tiene el siguiente formato:

• La primera línea contiene un entero positivo $K_i$: el número de valores posibles para $A_i$.
• Cada una de las siguientes $K_i$ líneas contiene dos enteros $V_{i,j}$ y $C_{i,j}$: un valor posible y el costo de elegir ese valor, respectivamente ($0 \le V_{i,j} \le 10^8$, $0 \le C_{i,j} \le 10^{13}$).

Se garantiza que la suma de $K_i$ es como máximo $3 \cdot 10^5$.

Salida

Imprime un entero: la puntuación máxima posible.

Ejemplos

Entrada 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

Salida 1

78

Entrada 2

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

Salida 2

-145