시간 제한메모리 제한제출정답맞힌 사람정답 비율
2.5 초 1024 MB22191583.333%

문제

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

길이 $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
W3sicHJvYmxlbV9pZCI6IjIwNTU4IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVjZmZjXHViOWFjXHVjNjQwIFx1YzIxOFx1YzVmNCIsImRlc2NyaXB0aW9uIjoiPHA+XHVjNzc0IFx1YjMwMFx1ZDY4Y1x1YzVkMCBcdWNmZmNcdWI5YWMgXHViYjM4XHVjODFjXHVhYzAwIFx1YWQ0OVx1YzdhNVx1ZDc4OCBcdWI5Y2VcdWIyZTRcdWIyOTQgXHVhYzgzXHVjNzQ0IFx1YzVlY1x1YjdlY1x1YmQ4NFx1YjRlNFx1YjNjNCBcdWIyMDhcdWNlNThcdWNjNThcdWM3NDQgXHVhYzgzXHVjNzc0XHViMmU0LiBcdWNmZmNcdWI5YWNcdWI5N2MgXHVjMGFjXHViNzkxXHVkNTU4XHViMjk0IFx1Y2Q5Y1x1YzgxY1x1YzljNFx1YjRlNFx1Yzc0MCBcdWMyMThcdWM1ZjRcdWM1ZDAgXHVjN2FjXHViYmY4XHVjNWM2XHViMjk0IFx1Y2ZmY1x1YjlhY1x1Yjk3YyBcdWQ1NThcdWIyOTQgXHViYjM4XHVjODFjXHViOTdjIFx1ZDU1OFx1YjA5OCBcdWIzNTQgXHViMGI0XHVhY2UwIFx1YzJmNlx1YzVjOFx1YzljMFx1YjljYywgXHVjNWVjXHViN2VjXHViZDg0XHVjNzU4IFx1YmMxOFx1YmMxY1x1Yzc3NCBcdWMyZWNcdWQ1NjAgXHVhYzgzIFx1YWMxOVx1YzU0NCBcdWIzMDBcdWMyZTAgXHVjZmZjXHViOWFjXHViNGU0XHVjNzc0IFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NFx1YjU0YyBcdWMyMThcdWM1ZjRcdWM3NDQgXHVhZDZjXHVkNTU4XHViMjk0IFx1YmIzOFx1YzgxY1x1Yjk3YyBcdWI5Y2NcdWI0ZTRcdWFlMzBcdWI4NWMgXHVkNTg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFlMzhcdWM3NzQgJE4kXHVjNzU4IFx1YzIxOFx1YzVmNCAkQSRcdWM1ZDAgXHVhZDZjXHVhYzA0IFx1Y2Q1Y1x1YjMxM1x1YWMxMiBcdWNmZmNcdWI5YWNcdWI5N2MgXHVkNTYwIFx1YWM4M1x1Yzc3OFx1YjM3MCwgJFtpLGpdJFx1YzVkMFx1YjI5NCAkUV97aSxqfSRcdWJjODggXHVjZmZjXHViOWFjXHViOTdjIFx1ZDU2MCBcdWFjODNcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzU0NFx1YzljMSBcdWMyMThcdWM1ZjQgJEEkXHVjNzU4IFx1YWMxMlx1Yzc0MCBcdWM4MTVcdWQ1NzRcdWM5YzBcdWM5YzAgXHVjNTRhXHVjNTU4XHViMmU0LiAkMSRcdWJkODBcdWQxMzAgJE4kXHVhZTRjXHVjOWMwXHVjNzU4IFx1YWMwMSAkaSRcdWM1ZDAgXHViMzAwXHVkNTc0LCAkQV9pJFx1Yzc1OCBcdWFjMTJcdWM3M2NcdWI4NWMgXHVjMTFjXHViODVjIFx1YjJlNFx1Yjk3OCAkS19pJFx1YWMxY1x1Yzc1OCBcdWFjMTIgXHVjOTExIFx1ZDU1OFx1YjA5OFx1Yjk3YyBcdWMxMjBcdWQwZGRcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjI5NFx1YjM3MCwgJGokXHViYzg4XHVjOWY4IFx1YWMxMlx1Yzc0MCAkVl97aSxqfSRcdWM3NzRcdWJhNzAgXHVhZGY4IFx1YWMxMlx1Yzc0NCBcdWFjZTBcdWI5NzRcdWIyOTQgXHViZTQ0XHVjNmE5XHVjNzQwICRDX3tpLGp9JFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNmIwXHViOWFjXHVjNzU4IFx1YmFhOVx1ZDQ1Y1x1YjI5NCBcdWM4MDFcdWM4MDhcdWQ3ODggXHVjMjE4XHVjNWY0ICRBJFx1Yjk3YyBcdWFjZThcdWI3N2MgXHVhZDZjXHVhYzA0IFx1Y2ZmY1x1YjlhY1x1YjRlNFx1Yzc1OCBcdWFjYjBcdWFjZmNcdWI0ZTRcdWM3NTggXHVkNTY5XHVjNWQwXHVjMTFjIFx1YWMxMlx1YjRlNFx1Yzc0NCBcdWFjZTBcdWI5NzRcdWIyOTQgXHViZTQ0XHVjNmE5XHVjNzQ0IFx1YmU4MCBcdWFjMTJcdWM3NDQgXHVjZDVjXHViMzAwXHVkNjU0XHVkNTU4XHViMjk0IFx1YWM4M1x1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYiBcdWM5MDRcdWM1ZDAgJE4kXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gJCgxIFxcbGVxIE4gXFxsZXEgMzAwKSQ8XC9wPlxyXG5cclxuPHA+XHVjNzc0XHVkNmM0ICROJFx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDAgXHVhYzc4XHVjY2QwLCAkUV97aSxqfSRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAkaSRcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0ICRRX3tpLGl9JFx1YmQ4MFx1ZDEzMCAkUV97aSxOfSRcdWFlNGNcdWM5YzBcdWM3NTggXHVjMjE4XHVhYzAwIFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWI0MThcdWM1YjQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAkKDAgXFxsZXEgUV97aSxqfSBcXGxlcSA5OTkpJDxcL3A+XHJcblxyXG48cD5cdWM3NzRcdWQ2YzQgJE4kXHVhYzFjXHVjNzU4IFx1Yzc3OFx1YjM3MVx1YzJhNFx1YzVkMCBcdWIzMDBcdWQ1NzQgXHVhYzEyXHVjNzU4IFx1ZDZjNFx1YmNmNFx1YjRlNFx1Yzc1OCBcdWM4MTVcdWJjZjRcdWFjMDAgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc0MCBcdWQ2MTVcdWMyZGRcdWM3M2NcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPlx1Y2NhYiBcdWM5MDRcdWM1ZDAgJEtfaSRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAkKDEgXFxsZXEgS19pKSQ8XC9saT5cclxuXHQ8bGk+XHVjNzc0XHVkNmM0ICRLX2kkXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMCBcdWFjNzhcdWNjZDAgJFZfe2ksan0kXHVjNjQwICRDX3tpLGp9JFx1YWMwMCBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHViNDE4XHVjNWI0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gJCgwIFxcbGVxIFZfe2ksan0gXFxsZXEgMTBeOCwgMCBcXGxlcSBDX3tpLGp9IFxcbGVxIDEwXnsxM30pJDxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPiRLX2kkXHVjNzU4IFx1ZDU2OVx1Yzc0MCAkMzAwXFwsMDAwJCBcdWM3NzRcdWQ1NThcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhZDZjXHVhYzA0IFx1Y2ZmY1x1YjlhY1x1YjRlNFx1Yzc1OCBcdWFjYjBcdWFjZmNcdWI0ZTRcdWM3NTggXHVkNTY5XHVjNWQwXHVjMTFjIFx1YWMxMlx1YjRlNFx1Yzc0NCBcdWFjZTBcdWI5NzRcdWIyOTQgXHViZTQ0XHVjNmE5XHVjNzQ0IFx1YmU4MCBcdWFjMTJcdWM3NTggXHVjZDVjXHViMzEzXHVhYzEyXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIyMDU1OCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkdlbmVyYXRlIFRoZSBBcnJheSIsImRlc2NyaXB0aW9uIjoiPHA+Q29uc2lkZXIgYW4gYXJyYXkgJEEkIG9mIGxlbmd0aCAkTiQuIFlvdSBhcmUgcGxhbm5pbmcgdG8gZG8gc2V2ZXJhbCBxdWVyaWVzOiBmb3IgYSBzZWdtZW50ICRbaSwgal0kIG9mIHRoZSBhcnJheSwgZmluZCB0aGUgbWF4aW11bSB2YWx1ZSBvbiB0aGF0IHNlZ21lbnQgb2YgdGhlIGFycmF5LiBUaGUgcXVlcnkgZm9yIHRoZSBpbmRpY2VzICRpJCBhbmQgJGokIHdpbGwgYmUgZG9uZSAkUV97aSwgan0kIHRpbWVzLjxcL3A+XHJcblxyXG48cD5CdXQgdGhlIGFycmF5IGlzIG5vdCBnaXZlbiwgYW5kIHlvdSBhcmUgZ29pbmcgdG8gYnVpbGQgaXQgcmlnaHQgbm93LjxcL3A+XHJcblxyXG48cD5Gb3IgZWFjaCAkaSQgZnJvbSAkMSQgdG8gJE4kLCB5b3UgY2FuIHNlbGVjdCBvbmUgb2YgJEtfaSQgZGlmZmVyZW50IHZhbHVlcyAkVl97aSwgan0kIGFzIHRoZSB2YWx1ZSBvZiAkQV9pJCwgYW5kIHRoZSByZXNwZWN0aXZlIGNvc3RzIG9mIGNob29zaW5nIHRoZXNlIHZhbHVlcyBhcmUgJENfe2ksIGp9JC48XC9wPlxyXG5cclxuPHA+QWZ0ZXIgYWxsIHF1ZXJpZXMsIHlvdXIgPGVtPnNjb3JlPFwvZW0+IHdpbGwgYmUgdGhlIHN1bSBvZiB0aGUgcmVzdWx0cyBvZiBhbGwgdGhlIGludGVydmFsIHF1ZXJpZXMgeW91IGFyZSBwbGFubmluZyB0byBkbywgbWludXMgdGhlIGNvc3Qgb2YgY2hvb3NpbmcgdGhlIHZhbHVlcyAkQV9pJC4gRmluZCB0aGUgbWF4aW11bSBwb3NzaWJsZSBzY29yZSB0aGF0IGNhbiBiZSBhY2hpZXZlZC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPkZpcnN0IGxpbmUgb2YgdGhlIGlucHV0IGNvbnRhaW5zIG9uZSBpbnRlZ2VyICROJCAoJDEgXFxsZXEgTiBcXGxlcSAzMDAkKS48XC9wPlxyXG5cclxuPHA+VGhlbiAkTiQgbGluZXMgZm9sbG93LiBUaGUgJGkkLXRoIG9mIHRob3NlIGxpbmVzIGNvbnRhaW5zIGludGVnZXJzIGZyb20gJFFfe2ksIGl9JCB0byAkUV97aSwgTn0kICgkMCBcXGxlcSBRX3tpLCBqfSBcXGxlcSA5OTkkKS4gVGhlIHF1ZXJ5IGZvciB0aGUgbWF4aW11bSBlbGVtZW50IGluIHRoZSBhcnJheSBiZXR3ZWVuICRBX2kkIGFuZCAkQV9qJCBpbmNsdXNpdmVseSBzaGFsbCBiZSBwZXJmb3JtZWQgZXhhY3RseSAkUV97aSwgan0kIHRpbWVzLjxcL3A+XHJcblxyXG48cD5BZnRlciB0aGF0LCB0aGUgaW5wdXQgZGVzY3JpYmVzIHBvc3NpYmxlIHZhbHVlcyBvZiAkQV9pJCBmb3IgZWFjaCAkaSQgZnJvbSAkMSQgdG8gJE4kLiBUaGUgJGkkLXRoIGRlc2NyaXB0aW9uIGhhcyB0aGUgZm9sbG93aW5nIGZvcm1hdDo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5UaGUgZmlyc3QgbGluZSBjb250YWlucyBhIHBvc2l0aXZlIGludGVnZXIgJEtfaSQ6IHRoZSBudW1iZXIgb2YgcG9zc2libGUgdmFsdWVzIGZvciAkQV9pJC48XC9saT5cclxuXHQ8bGk+RWFjaCBvZiB0aGUgZm9sbG93aW5nICRLX2kkIGxpbmVzIGNvbnRhaW5zIHR3byBpbnRlZ2VycyAkVl97aSwgan0kIGFuZCAkQ197aSwgan0kOiBhIHBvc3NpYmxlIHZhbHVlIGFuZCB0aGUgY29zdCBvZiBwaWNraW5nIHRoYXQgdmFsdWUsIHJlc3BlY3RpdmVseSAoJDAgXFxsZXEgVl97aSwgan0gXFxsZXEgMTBeOCQsICQwIFxcbGVxIENfe2ksIGp9IFxcbGVxIDEwXnsxM30kKS48XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5JdCBpcyBndWFyYW50ZWVkIHRoYXQgdGhlIHN1bSBvZiAkS19pJCBpcyBhdCBtb3N0ICQzIFxcY2RvdCAxMF41JC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5QcmludCBvbmUgaW50ZWdlcjogdGhlIG1heGltdW0gcG9zc2libGUgc2NvcmUuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==