問題文

$K$ 個の数列が与えられます。 $i$ 個目の数列 $A_i$ の長さは $N_i$ です。

これらを使って高橋君と青木君がゲームをします。 全ての数列が長さ $1$ になるまで、高橋君と青木君が交互に以下の操作を行います。

• 長さが $2$ 以上の数列を $1$ つ選び、その最初の要素或いは最後の要素を削除する。

高橋君が先に操作を行います。最後に残る $K$ 個の要素の総和を、高橋君は最大化したいと、青木君は最小化したいと考えています。

両者最適に行動するとき、最後に残る $K$ 個の要素の総和を答えてください。

制約

• 入力は全て整数
• $1 \\leq K \\leq 2 \\times 10^5$
• $1 \\leq N_i$
• $\\sum_i N_i \\leq 2 \\times 10^5$
• $1 \\leq A_{i, j} \\leq 10^9$

入力

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

$K$ $N_1$ $A_{1, 1}$ $A_{1, 2}$ $\\cdots$ $A_{1, N_1}$ $N_2$ $A_{2, 1}$ $A_{2, 2}$ $\\cdots$ $A_{2, N_2}$ $\\vdots$ $N_K$ $A_{K, 1}$ $A_{K, 2}$ $\\cdots$ $A_{K, N_K}$

出力

答えを出力せよ。

入力例 1

2
3 1 2 3
2 1 10

出力例 1

12

ゲームの進行の一例を示します。

• 高橋君が $A_2$ の最初の要素を削除する。現在の数列の状態は、 $A_1 = \\left(1, 2, 3\\right), A_2 = \\left(10\\right)$ である。
• 青木君が $A_1$ の最後の要素を削除する。現在の数列の状態は、 $A_1 = \\left(1, 2\\right), A_2 = \\left(10\\right)$ である。
• 高橋君が $A_1$ の最初の要素を削除する。現在の数列の状態は、 $A_1 = \\left(2\\right), A_2 = \\left(10\\right)$ である。全ての数列の長さが $1$ となった為、ゲームが終了する。

このとき、最後に残る $K$ 個の要素の総和は $12$ です。尚、このゲームの進行が両者にとって最適な行動であるとは限りません。

入力例 2

8
1 2
2 1 2
3 1 2 1
4 1 1 1 2
5 1 1 2 2 1
6 2 2 2 2 1 1
7 1 2 1 1 2 2 2
8 2 2 2 1 1 1 1 2

出力例 2

12