题目描述

Artem 向女孩 Olya 提议了一个游戏。有一个包含 $n$ 个数组的列表，第 $i$ 个数组包含 $m_i \ge 2$ 个正整数 $a_{i,1}, a_{i,2}, \ldots, a_{i,m_i}$。

Olya 可以从每个数组中至多移动一个（也可以不移动）整数到另一个数组。注意，每个数组只能向外移动一次整数，但一个数组可以多次接收整数，且所有移动是同时进行的。

这些数组列表的美丽值定义为 $\sum_{i=1}^n \min_{j=1}^{m_i} a_{i,j}$。也就是说，对于每个数组，取其中的最小值，然后将这些最小值相加。

游戏的目标是最大化数组列表的美丽值。请帮助 Olya 赢得这个有挑战性的游戏！

输入格式

每个测试包含多个测试用例。第一行包含一个整数 $t$（$1 \le t \le 25000$）——测试用例的数量。接下来是每个测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 25000$）——数组的数量。

接下来是每个数组的描述。每个数组的描述包含两行。

第一行包含一个整数 $m_i$（$2 \le m_i \le 50000$）——第 $i$ 个数组的元素个数。

第二行包含 $m_i$ 个整数 $a_{i,1}, a_{i,2}, \ldots, a_{i,m_i}$（$1 \le a_{i,j} \le 10^9$）——第 $i$ 个数组的元素。

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

输出格式

对于每个测试用例，输出一行一个整数，表示 Olya 能够获得的数组列表的最大美丽值。

说明/提示

在第一个测试用例中，我们可以将第二个数组中的整数 $3$ 移动到第一个数组。此时美丽值为 $\min(1, 2, 3) + \min(4) = 5$。可以证明这是最大可能的美丽值。

在第二个测试用例中，只有一个数组，无论如何移动，美丽值都是 $\min(100, 1, 6) = 1$。

由 ChatGPT 4.1 翻译

样例

3
2
2
1 2
2
4 3
1
3
100 1 6
3
4
1001 7 1007 5
3
8 11 6
2
2 9

5
1
19