길이가 $N$인 배열 $A$를 고려하자. 당신은 배열의 구간 $[i, j]$에 대해 해당 구간의 최댓값을 찾는 여러 쿼리를 수행할 계획이다. 인덱스 $i$와 $j$에 대한 쿼리는 $Q_{i,j}$번 수행될 것이다.

하지만 배열은 아직 주어지지 않았으며, 지금 바로 배열을 구성해야 한다.

각 $i$ ($1 \le i \le N$)에 대해, $A_i$의 값으로 $K_i$개의 서로 다른 값 $V_{i,j}$ 중 하나를 선택할 수 있으며, 각 값을 선택하는 데 드는 비용은 $C_{i,j}$이다.

모든 쿼리가 끝난 후, 당신의 점수는 계획한 모든 구간 쿼리 결과의 합에서 $A_i$ 값을 선택하는 데 든 비용을 뺀 값이다. 얻을 수 있는 최대 점수를 구하시오.

입력

첫 번째 줄에는 정수 $N$ ($1 \le N \le 300$)이 주어진다.

그다음 $N$개의 줄이 주어진다. $i$번째 줄에는 $Q_{i,i}$부터 $Q_{i,N}$까지의 정수 ($0 \le Q_{i,j} \le 999$)가 주어진다. $A_i$부터 $A_j$까지(양 끝 포함)의 구간에서 최댓값을 구하는 쿼리는 정확히 $Q_{i,j}$번 수행된다.

그 후, 각 $i$ ($1 \le i \le N$)에 대해 $A_i$가 가질 수 있는 값들이 주어진다. $i$번째 설명은 다음 형식을 따른다.

• 첫 번째 줄에는 $A_i$가 가질 수 있는 값의 개수인 양의 정수 $K_i$가 주어진다.
• 이어지는 $K_i$개의 줄에는 각각 $V_{i,j}$와 $C_{i,j}$라는 두 정수가 주어진다. 이는 각각 가능한 값과 그 값을 선택할 때의 비용을 의미한다 ($0 \le V_{i,j} \le 10^8$, $0 \le C_{i,j} \le 10^{13}$).

$K_i$의 합은 최대 $3 \cdot 10^5$임이 보장된다.

출력

최대 점수를 정수 하나로 출력하시오.

예제

입력 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

출력 1

78

입력 2

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

출력 2

-145