F - Deque Game 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 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}

出力

答えを出力せよ。

入力例 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

Score : 800 points

Problem Statement

We have K sequences. The i-th sequence A_i has the length of N_i.

Takahashi and Aoki will play a game using these. They will alternately do the following operation until the length of every sequence becomes 1:

  • Choose a sequence of length at least 2, and delete its first or last element.

Takahashi goes first. Takahashi wants to maximize the sum of the K elements remaining in the end, while Aoki wants to minimize it.

Find the sum of the K elements remaining in the end when both players play optimally.

Constraints

  • All values in input are integers.
  • 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

Input

Input is given from Standard Input in the following format:

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}

Output

Print the answer.

Sample Input 1

2
3 1 2 3
2 1 10

Sample Output 1

12

Here is one possible progression of the game:

  • Takahashi deletes the first element of A_2. Now we have A_1 = \left(1, 2, 3\right), A_2 = \left(10\right).
  • Aoki deletes the last element of A_1. Now we have A_1 = \left(1, 2\right), A_2 = \left(10\right).
  • Takahashi deletes the first element of A_1. Now we have A_1 = \left(2\right), A_2 = \left(10\right). The length of every sequence has become 1, so the game ends.

In this case, the sum of the K elements remaining in the end is 12. Note that the players may have made suboptimal moves here.

Sample Input 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

Sample Output 2

12