쿼리와 수열

이 대회에 쿼리 문제가 굉장히 많다는 것을 여러분들도 눈치챘을 것이다. 쿼리를 사랑하는 출제진들은 수열에 재미없는 쿼리를 하는 문제를 하나 더 내고 싶었지만, 여러분의 반발이 심할 것 같아 대신 쿼리들이 주어졌을 때 수열을 구하는 문제를 만들기로 했다.

길이 $N$의 수열 $A$에 구간 최댓값 쿼리를 할 것인데, 구간 $[i,j]$에는 $Q_{i,j}$번 쿼리를 할 것이다.

아직 수열 $A$의 값은 정해지지 않았다. $1$부터 $N$까지의 각 $i$에 대해, $A_i$의 값으로 서로 다른 $K_i$개의 값 중 하나를 선택할 수 있다. $j$번째 값은 $V_{i,j}$이며, 그 값을 고르는 비용은 $C_{i,j}$이다.

우리의 목표는 수열 $A$를 적절히 골라, 구간 쿼리들의 결과의 합에서 값들을 고르는 데 든 비용을 뺀 값을 최대화하는 것이다.

첫 줄에 $N$이 주어진다. ($1 \leq N \leq 300$)

이후 $N$개의 줄에 걸쳐 $Q_{i,j}$가 주어진다. $i$번째 줄에는 $Q_{i,i}$부터 $Q_{i,N}$까지의 수가 공백으로 구분되어 주어진다. ($0 \leq Q_{i,j} \leq 999$)

이후 $N$개의 인덱스에 대해 값의 후보들의 정보가 다음과 같은 형식으로 주어진다.

• 첫 줄에 $K_i$가 주어진다. ($1 \leq K_i$)
• 이후 $K_i$개의 줄에 걸쳐 $V_{i,j}$와 $C_{i,j}$가 공백으로 구분되어 주어진다. ($0 \leq V_{i,j} \leq 10^8$, $0 \leq C_{i,j} \leq 10^{13}$)

$K_i$의 합은 $300\,000$ 이하이다.

구간 쿼리들의 결과의 합에서 값들을 고르는 비용을 뺀 값의 최댓값을 출력한다.