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