CF1859B.Olya and Game with Arrays

Artem suggested a game to the girl Olya. There is a list of $n$ arrays, where the $i$-th array contains $m_i \ge 2$ positive integers $a_{i,1}, a_{i,2}, \ldots, a_{i,m_i}$.

Olya can move at most one (possibly $0$) integer from each array to another array. Note that integers can be moved from one array only once, but integers can be added to one array multiple times, and all the movements are done at the same time.

The beauty of the list of arrays is defined as the sum $\sum_{i=1}^n \min_{j=1}^{m_i} a_{i,j}$. In other words, for each array, we find the minimum value in it and then sum up these values.

The goal of the game is to maximize the beauty of the list of arrays. Help Olya win this challenging game!

阿尔捷姆向女孩奥莉娅提议了一个游戏。现在有 $n$ 个数组构成的列表，其中第 $i$ 个数组包含 $m_i \ge 2$ 个正整数 $a_{i,1}, a_{i,2}, \ldots, a_{i,m_i}$。

奥莉娅可以从每个数组中至多移动一个（也可以不移动）整数到另一个数组。注意：每个整数最多只能从其所在数组中移出一次，但可以被多次添加到同一个目标数组中；且所有移动操作是同时进行的。

该数组列表的“美观度”定义为 $\sum_{i=1}^n \min_{j=1}^{m_i} a_{i,j}$。换言之，对每个数组，我们取其中的最小值，再将所有这些最小值相加。

本游戏的目标是使数组列表的美观度最大化。请帮助奥莉娅赢得这场富有挑战性的游戏！

Each test consists of multiple test cases. The first line contains a single integer $t$ ($1 \le t \le 25000$) — the number of test cases. The description of test cases follows.

The first line of each test case contains a single integer $n$ ($1 \le n \le 25000$) — the number of arrays in the list.

This is followed by descriptions of the arrays. Each array description consists of two lines.

The first line contains a single integer $m_i$ ($2 \le m_i \le 50000$) — the number of elements in the $i$-th array.

The next line contains $m_i$ integers $a_{i, 1}, a_{i, 2}, \ldots, a_{i, m_i}$ ($1 \le a_{i,j} \le 10^9$) — the elements of the $i$-th array.

It is guaranteed that the sum of $m_i$ over all test cases does not exceed $50000$.

每个测试包含多个测试用例。第一行包含一个整数 $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$。

For each test case, output a single line containing a single integer — the maximum beauty of the list of arrays that Olya can achieve.

对于每个测试用例，输出一行，包含一个整数——Olya 能够达到的数组列表的最大美观度。

In the first test case, we can move the integer $3$ from the second array to the first array. Then the beauty is $\min(1, 2, 3) + \min(4) = 5$. It can be shown that this is the maximum possible beauty.

In the second test case, there is only one array, so regardless of the movements, the beauty will be $\min(100, 1, 6) = 1$.

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

在第二个测试用例中，只有一个数组，因此无论进行何种移动，美观度均为 $\min(100, 1, 6) = 1$。