시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2.5 초 1024 MB 14 12 9 81.818%

문제

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

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

출력

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

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

출처

High School > 경기과학고등학교 > 나는코더다 2020 송년대회 G번