쿼리와 수열

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

길이 $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$ 이하이다.

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