← 返回题目列表

Codeforces · 1859/B

B. Olya 和数组游戏

中文机器翻译题面 查看原题

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

Olya 最多可以将一个(可能是 $$$0$$$)整数从每个数组移动到另一个数组。请注意,整数只能从一个数组中移动一次,但整数可以多次添加到一个数组中,并且所有移动都是同时完成的。

数组列表的美妙之处被定义为总和 $$$\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 可以实现的数组列表的最大美感。

示例

输入 #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

输出 #1

5
1
19

注意

在第一个测试用例中,我们可以将整数 $$$3$$$ 从第二个数组移动到第一个数组。那么美丽就是$$$\min(1, 2, 3) + \min(4) = 5$$$。可见,这就是最大可能的美。

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