题目背景

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

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

雨宫莲没有理会书包里传来的声音。他看着面前的 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$。

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

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

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

“……这也行？”