题目描述

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

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

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

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

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

输入格式

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

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

输出格式

答えを出力せよ。

题目大意

有 $K$ 个数列，第 $i$ 个数列的长度为 $N_i$，命名为 $A_i$。第 $i$ 个数列的第 $j$ 个元素被称为 $A_{i,j}$。

Takahashi 和 Aoki 在玩游戏。每一轮中，可以选择一个剩余元素数量 $>1$ 的数列，并删掉最前面或者最后面的元素。

Takahashi 先手。当每个数列都只剩下一个元素时，游戏结束。

定义一局游戏的得分为最后剩下的元素之和。Takahashi 想要最大化得分，而 Aoki 想要最小化得分。

假设两人都绝顶聪明，请输出最后的得分。

$1\le K,N_i,\sum N_i\le 2\times 10^5$，$1\le A_{i,j,}\le 10^9$。

2
3 1 2 3
2 1 10

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

提示

制約

• 入力は全て整数
• $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$

Sample Explanation 1

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