Taxi

Time Limit : 1 sec, Memory Limit : 262144 KB

タクシー

 

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

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

PCKタクシーの運転手は提示額の低い客の乗車を断り、提示額の高い客を乗車させることでPCK社の売り上げを上げている。

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

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

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

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

入力

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

$N$
$s_1$
$s_2$
$...$
$s_N$

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

$M$ $c_1$ $c_2$ ... $c_M$

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

出力

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

入出力例

入力例

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

出力例

45
?