AtCoder Regular Contest 056

D - サケノミ


Time limit時間制限 : 2sec / Memory limitメモリ制限 : 256MB

問題文

あなたは風変わりなバーに来ています。このバーでは、N種類のドリンクがあり、あなたは初めにN個のグラスを与えられます。i番目のグラスはi番目のドリンクに対応しており、i番目のドリンクのみが注がれます。また、それぞれのドリンクに対し、美味しさw_iが定まっています。初めに、全てのグラスは空です。

それぞれのドリンクは、何回か決まった時刻に補充されます。 すなわち、 時間t_{i,j}(1≦j≦M_i)i番目のグラスが空ならば、i番目のグラスにi番目のドリンクが注がれます。

あなたは、好きな奇数時刻に、全てのグラスに入っているドリンクを全て飲み干すことができます。一部のドリンクのみを飲む行為は禁止されています。 飲んだドリンクの美味しさの総和の最大値を求めるプログラムを書いてください。ただし、同じドリンクを複数回飲んだときも、美味しさは重複して計算されることに注意してください。


制約

  • 1 ≦ N ≦ 5*10^5
  • 2 ≦ t_{i,j} ≦ 10^6
  • t_{i,j} < t_{i,j+1}
  • t_{i,j}は偶数である
  • Σ M_i ≦ 5*10^5
  • 1 ≦ M_i
  • -10^9 ≦ w_i ≦ 10^9

部分点

  • t_{i,j} ≦ 1,000 かつ N ≦ 1,000 を満たすテストケース全てに正解した場合、部分点として30点が与えられる。

入力

入力は以下の形式で標準入力から与えられる。

N
w_1 ... w_N
M_1 t_{1,1} ... t_{1,M_1}
:
M_N t_{N,1} ... t_{N,M_N}

出力

1行目に、美味しさの総和を出力せよ。


入力例1

3
2 5 -6
1 2
2 4 10
2 4 8

出力例1

6

時刻911にグラスにあるドリンクを全て飲み干します。 時刻9では、3つ全てドリンクが注がれているため、美味しさ2+5-6=1を得ます。 時刻11では、2番目のドリンクのみ注がれているため、美味しさ5を得ます。合計6となります。


入力例2

3
2 5 -6
2 2 8
2 4 10
2 4 10

出力例2

3

入力例3

3
3 5 -4
2 2 8
4 4 6 10 12
4 2 4 8 10

出力例3

18

入力例4

3
-2 -2 -2
2 2 8
4 4 6 10 12
4 2 4 8 10

出力例4

0

Submit提出する