310608: CF1859B. Olya and Game with Arrays

B. Olya and Game with Arraystime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

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!

Input

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$.

Output

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

ExampleInput

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

Output

5
1
19

Note

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$.

题目大意：
奥莉娅和数组游戏

阿蒂姆向奥莉娅建议了一个游戏。有一个长度为 $ n $ 的数组列表，其中第 $ i $ 个数组包含 $ m_i \geq 2 $ 个正整数 $ a_{i,1}, a_{i,2}, \ldots, a_{i,m_i} $。

奥莉娅可以从每个数组中最多移动一个（也可能 0 个）整数到另一个数组。注意，整数只能从一个数组移动一次，但可以多次添加到一个数组中，所有移动是同时进行的。

数组列表的美丽值定义为 $\sum_{i=1}^n \min_{j=1}^{m_i} a_{i,j}$。换句话说，对于每个数组，我们找到数组中的最小值，然后将这些值相加。

游戏的目的是最大化数组列表的美丽值。帮助奥莉娅赢得这个挑战游戏！

输入数据格式：
每个测试包含多个测试用例。第一行包含一个整数 $ t $ ($ 1 \leq t \leq 25000 $) —— 测试用例的数量。接下来是测试用例的描述。

每个测试用例的第一行包含一个整数 $ n $ ($ 1 \leq n \leq 25000 $) —— 数组列表中的数组数量。

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

第一行包含一个整数 $ m_i $ ($ 2 \leq m_i \leq 50000 $) —— 第 $ i $ 个数组的元素数量。

下一行包含 $ m_i $ 个整数 $ a_{i, 1}, a_{i, 2}, \ldots, a_{i, m_i} $ ($ 1 \leq a_{i,j} \leq 10^9 $) —— 第 $ i $ 个数组的元素。

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

输出数据格式：
对于每个测试用例，输出一行，包含一个整数 —— 奥莉娅可以实现的数组列表的最大美丽值。

示例输入输出（请参考原文以获取详细示例）：
输入：
```
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
```

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

在第二个测试用例中，只有一个数组，所以无论怎样移动，美丽值都将是 $ \min(100, 1, 6) = 1 $。题目大意： 奥莉娅和数组游戏 阿蒂姆向奥莉娅建议了一个游戏。有一个长度为 $ n $ 的数组列表，其中第 $ i $ 个数组包含 $ m_i \geq 2 $ 个正整数 $ a_{i,1}, a_{i,2}, \ldots, a_{i,m_i} $。 奥莉娅可以从每个数组中最多移动一个（也可能 0 个）整数到另一个数组。注意，整数只能从一个数组移动一次，但可以多次添加到一个数组中，所有移动是同时进行的。 数组列表的美丽值定义为 $\sum_{i=1}^n \min_{j=1}^{m_i} a_{i,j}$。换句话说，对于每个数组，我们找到数组中的最小值，然后将这些值相加。 游戏的目的是最大化数组列表的美丽值。帮助奥莉娅赢得这个挑战游戏！ 输入数据格式： 每个测试包含多个测试用例。第一行包含一个整数 $ t $ ($ 1 \leq t \leq 25000 $) —— 测试用例的数量。接下来是测试用例的描述。 每个测试用例的第一行包含一个整数 $ n $ ($ 1 \leq n \leq 25000 $) —— 数组列表中的数组数量。 接下来是数组的描述。每个数组描述包含两行。 第一行包含一个整数 $ m_i $ ($ 2 \leq m_i \leq 50000 $) —— 第 $ i $ 个数组的元素数量。 下一行包含 $ m_i $ 个整数 $ a_{i, 1}, a_{i, 2}, \ldots, a_{i, m_i} $ ($ 1 \leq a_{i,j} \leq 10^9 $) —— 第 $ i $ 个数组的元素。 保证所有测试用例的 $ m_i $ 之和不超过 $ 50000 $。 输出数据格式： 对于每个测试用例，输出一行，包含一个整数 —— 奥莉娅可以实现的数组列表的最大美丽值。 示例输入输出（请参考原文以获取详细示例）： 输入： ``` 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 ``` 注意： 在第一个测试用例中，我们可以将整数 3 从第二个数组移动到第一个数组。然后美丽值为 $ \min(1, 2, 3) + \min(4) = 5 $。可以证明这是可能的最大美丽值。 在第二个测试用例中，只有一个数组，所以无论怎样移动，美丽值都将是 $ \min(100, 1, 6) = 1 $。