题目描述

我们有 $K$ 个序列。第 $i$ 个序列 $A_i$ 的长度为 $N_i$。

高桥和青木将使用这些序列进行游戏。他们会轮流执行以下操作，直到每个序列的长度变为 $1$：

• 选择一个长度至少为 $2$ 的序列，并删除其第一个或最后一个元素。

高桥先开始。 高桥希望在最后剩下的 $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