AT_arc116_f [ARC116F] Deque Game

给定 $K$ 个数列。第 $i$ 个数列 $A_i$ 的长度为 $N_i$。 高桥君和青木君将用这些数列进行游戏。直到所有数列都变为长度 $1$，高桥君和青木君轮流进行以下操作： - 选择一个长度至少为 $2$ 的数列，删除其第一个元素或最后一个元素。 高桥君先手。高桥君希望最大化最后剩下的 $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}$

输出答案。

### 限制条件 - 所有输入均为整数。 - $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$ ### 样例说明 1 以下是游戏进行的一种情况： - 高桥君删除 $A_2$ 的第一个元素。此时各数列为 $A_1 = (1, 2, 3),\ A_2 = (10)$。 - 青木君删除 $A_1$ 的最后一个元素。此时各数列为 $A_1 = (1, 2),\ A_2 = (10)$。 - 高桥君删除 $A_1$ 的第一个元素。此时各数列为 $A_1 = (2),\ A_2 = (10)$。 所有数列长度都变为 $1$，游戏结束。此时最后剩下的 $K$ 个元素的总和为 $12$。注意，这种游戏过程不一定是双方的最优策略。 由 ChatGPT 4.1 翻译