Артём предложил девочке Оле сыграть в следующую игру. Есть список из \(n\) массивов, \(i\)-й массив содержит \(m_i \ge 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}\). Иными словами, для каждого массива мы находим значение минимального элемента в нём, после чего суммируем получившиеся значения.
Суть игры — сделать красоту списка массивов максимально возможной. Помогите Оле победить в этой нелегкой игре!
Выходные данные
Для каждого набора входных данных выведите одно целое число — максимальную красоту списка массивов, которую Оля может получить.
Примечание
В первом наборе входных данных можно переместить число \(3\) из второго массива в первый. Тогда красота равна \(\min(1, 2, 3) + \min(4) = 5\). Можно показать, что это максимально возможная красота.
Во втором наборе входных данных есть всего один массив, поэтому независимо от перемещений красота равна \(\min(100, 1, 6) = 1\).
Примеры
| № | Входные данные | Выходные данные |
|
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
|