配点 : $800$ 点

問題文

$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}$

出力

答えを出力せよ。

2
3 1 2 3
2 1 10

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$ です。尚、このゲームの進行が両者にとって最適な行動であるとは限りません。

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

12