You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

“潜入路线确认，装备检查完成，接下来——”

“接下来该睡觉了。”摩尔加纳说。

雨宫莲没有理会书包里传来的声音。他看着面前的 Persona 名单，决定在潜入殿堂前，再做最后一次调整。

双叶为这次行动编写了一套战力评估程序。为了避免某个小队在关键时刻掉链子，她决定用每个小队中最弱成员的能力值，作为这个小队的战力。

“为什么只看最弱的那个？”龙司问。

“因为你上次就是那个最弱的。”

“喂！”

题目描述

雨宫莲将所有 Persona 分成了 $n$ 个小队。第 $i$ 个小队有 $m_i$ 个 Persona，第 $j$ 个 Persona 的能力值为 $a_{i,j}$。每个小队最初至少有两个 Persona。

一个小队的战力定义为该小队中所有 Persona 能力值的最小值。总战力定义为所有小队战力之和。

正式行动前，雨宫莲可以进行一次调配，规则如下：

• 每个小队最多选出一个 Persona，将它转移到另一个小队，也可以不选。
• 一个小队可以接收来自其他小队的任意多个 Persona，也可以在送出 Persona 的同时接收其他 Persona。
• 所有转移同时进行，因此刚收到的 Persona 不能在本次调配中再次转移。

看着雨宫莲不断修改名单，摩尔加纳打了个哈欠：

“你最好真的能让这串数字变大，而不是单纯想晚点睡觉。”

请你帮助雨宫莲，求出调配后能够达到的最大总战力。

输入格式

第一行包含一个整数 $t$（$1 \le t \le 25000$），表示测试用例的数量。

对于每个测试用例：

第一行包含一个整数 $n$（$1 \le n \le 25000$），表示小队的数量。

接下来依次描述 $n$ 个小队，每个小队的描述占两行：

• 第一行包含一个整数 $m_i$（$2 \le m_i \le 50000$），表示该小队的 Persona 数量。
• 第二行包含 $m_i$ 个整数 $a_{i,1},a_{i,2},\ldots,a_{i,m_i}$（$1 \le a_{i,j} \le 10^9$），表示这些 Persona 的能力值。

保证所有测试用例中，所有 $m_i$ 的总和不超过 $50000$。

输出格式

对于每个测试用例，输出一行一个整数，表示调配后能够达到的最大总战力。

样例

3
2
2
1 2
2
4 3
1
3
10 1 6
3
3
5 7 10
3
6 8 11
2
2 9

5
1
19

样例说明

第一个测试用例中，可以将第二个小队中能力值为 $3$ 的 Persona 转移到第一个小队。

调配后：

• 第一个小队的能力值为 $[1,2,3]$，战力为 $1$。
• 第二个小队的能力值为 $[4]$，战力为 $4$。

总战力为 $1+4=5$，可以证明这是最大值。

第二个测试用例中，只有一个小队，无法向其他小队转移 Persona，因此总战力始终为 $1$。

第三个测试用例中，可以将第二个小队中能力值为 $6$ 的 Persona，以及第三个小队中能力值为 $2$ 的 Persona，都转移到第一个小队。

调配后三个小队的战力分别为 $2,8,9$，总战力为 $19$。

“等一下，”龙司指着第一个小队，“你怎么把他们都往这里送？”

雨宫莲把计算结果递给了他。

龙司看了看名单，又看了看数字。

“……这也行？”