2096 - 宇宙戦艦イヅア

問題

宇宙戦艦イヅアは、大事な決戦を前にできるだけ多くの燃料を搭載しようとしている。宇宙戦艦イヅアには燃料タンクと燃料ポンプがあり、燃料ポンプと資金を使って燃料タンクに給油できる。燃料タンクに入っている燃料の量を$Q$、燃料ポンプの力を$P$で、それぞれ表す。初めは両方とも０になっている。

給油のための操作は$N$回かけて行う。$i$回目に行うことができる操作の選択肢は$L_i$個あり、この中のどれか１つを選択する。それぞれの選択では、使うことのできる資金が整数値Aで与えられ、以下のどちらかの操作を行うことができる。

1. 給油：ポンプと資金を使って給油を行う。給油後の$Q$の値は$Q+P+A$となる。
2. 燃料ポンプの増強：資金を使ってポンプの増強を行う。増強後の$P$の値は$P+A$となる。

給油のための操作を$N$回行った時、最大でどれくらいの燃料の量を搭載できるだろうか。

与えられた給油のための操作を$N$回行った際に得られる$Q$の最大値を求めるプログラムを作成せよ。

入力

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

$N$
$op_1$
$op_2$
:
$op_N$

１行目に操作の回数$N$ ($1 \leq N \leq 2,000$)が与えられる。続く$N$行に、$i$回目に選択できる操作の情報$op_i$が与えられる。操作の情報$op_i$は、以下の形式で与えられる。

$L_i$ $T_{i1}$ $A_{i1}$ $T_{i2}$ $A_{i2}$ ... $T_{iL_i}$ $A_{iL_i}$

１行に、$i$回目の操作の選択肢の個数$L_i$ ($L_i \geq 1$ かつ $N \leq L_1+L_2+...+L_N \leq 200,000=2\times10^5$)、続いて、$j$番目の選択肢の情報$T_{ij}$ ($T_{ij}=1$または$2$)と$A_{ij}$ ($1 \leq A_{ij} \leq 100,000=10^5$)が、$L_i$ 個続けて与えられる。ただし、$T_{ij}$が$1$のときはその操作が給油操作であること、$T_{ij}$が$2$のときはその操作が燃料ポンプの増強操作であることを示す。また、$j \ne k$ならば、$T_{ij} \ne T_{ik}$または$A_{ij} \ne A_{ik}$である。

出力

$Q$の最大値を１行に出力する。

入出力例

入力例

3
2 1 7 2 5
2 1 3 2 1
1 1 10

出力例

23

1回目に$A=5$のポンプの増強操作を選ぶ。2回目に$A=3$の給油操作を選ぶ。3回目に$A=10$の給油操作を選ぶと、燃料の量$Q＝23$となる。