問題文

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

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

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

入力

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

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

時刻9と11にグラスにあるドリンクを全て飲み干します。 時刻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