Изменения рейтингов за последние раунды временно удалены. Скоро они будут возвращены. ×

G. Generate The Array
time limit per test
2 с
memory limit per test
1024 mebibytes
input
standard input
output
standard output

Consider an array $$$A$$$ of length $$$N$$$. You are planning to do several queries: for a segment $$$[i, j]$$$ of the array, find the maximum value on that segment of the array. The query for the indices $$$i$$$ and $$$j$$$ will be done $$$Q_{i, j}$$$ times.

But the array is not given, and you are going to build it right now.

For each $$$i$$$ from $$$1$$$ to $$$N$$$, you can select one of $$$K_i$$$ different values $$$V_{i, j}$$$ as the value of $$$A_i$$$, and the respective costs of choosing these values are $$$C_{i, j}$$$.

After all queries, your score will be the sum of the results of all the interval queries you are planning to do, minus the cost of choosing the values $$$A_i$$$. Find the maximum possible score that can be achieved.

Input

First line of the input contains one integer $$$N$$$ ($$$1 \leq N \leq 300$$$).

Then $$$N$$$ lines follow. The $$$i$$$-th of those lines contains integers from $$$Q_{i, i}$$$ to $$$Q_{i, N}$$$ ($$$0 \leq Q_{i, j} \leq 999$$$). The query for the maximum element in the array between $$$A_i$$$ and $$$A_j$$$ inclusively shall be performed exactly $$$Q_{i, j}$$$ times.

After that, the input describes possible values of $$$A_i$$$ for each $$$i$$$ from $$$1$$$ to $$$N$$$. The $$$i$$$-th description has the following format:

  • The first line contains a positive integer $$$K_i$$$: the number of possible values for $$$A_i$$$.
  • Each of the following $$$K_i$$$ lines contains two integers $$$V_{i, j}$$$ and $$$C_{i, j}$$$: a possible value and the cost of picking that value, respectively ($$$0 \leq V_{i, j} \leq 10^8$$$, $$$0 \leq C_{i, j} \leq 10^{13}$$$).

It is guaranteed that the sum of $$$K_i$$$ is at most $$$3 \cdot 10^5$$$.

Output

Print one integer: the maximum possible score.

Examples
Input
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
Output
78
Input
2
1 1
1
2
1 100
2 50
1
1 100
Output
-145