008 - タクシー

問題文

会津都市のPCK社が運営するPCKタクシーはユニークな料金形態を採用しており、料金は客が決めることが出来る。今日も駅のタクシー乗り場では、多くの人が列をつくっている。

駅には、横N列にPCK社のタクシー乗り場が設置されている。各乗り場には1からNまでの番号が順番に付いており、タクシーが1台ずつ停まっている。また、各乗り場にはタクシーを待つ客が並んでおり、それぞれの客が払う料金はあらかじめわかっている。

i 番目の乗り場にいる運転手は、客を乗せ出発するまで以下の行動を好きな順番で何度でも行うことが出来る。

1. i 番目の乗り場の列の先頭の客をタクシーに乗せる。
2. i 番目の乗り場の列の先頭の客の乗車を断る。断られた客は列から消える。
3. i + 1 番目のタクシー乗り場に他のタクシーが存在しなければ、そこに移動する。ただし、N 番目の乗り場にいる場合は、公道に出てタクシー乗り場を去る。

あなたの仕事は、事前調査で得られた客の希望料金の表を基に、PCK社の売り上げを最大化することである。なお、1台のタクシーには最大一人の客を乗せることができる。

課題

タクシー乗り場の数と、各タクシー乗り場に並んでいる客の情報が与えられたとき、売り上げの総和の最大値を求めよ。

入力・出力

入力

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

N
s1
s2
:
sN

1行目にタクシー乗り場の数N(1≦N≦300,000)が与えられる。続くN行に、i番目のタクシー乗り場に並んでいる客の情報s_iが与えられる。各情報s_iは以下の形式で与えられる。

M c1 c2 … cM

最初の整数M(1≦M≦300,000)が、このタクシー乗り場に並んでいる人の数を表す。それに続いて、この乗り場のj番目に並んでいる客が払う料金c_j(1≦c_j≦10,000)が与えられる。

ただし、タクシー乗り場に並んでいる客の総数は300,000人以下である。

出力

売り上げの最大値を1行に出力する。

入出力例

入力例

3
3 8 10 1
4 7 1 2 15
3 11 8 19

出力例

45