Это сложная версия задачи, отличающаяся более высокими ограничениями.
Вам дана прямоугольная матрица \(a\) размером \(n \times m\). За один ход вы можете выбрать произвольный столбец и циклически сдвинуть все элементы в этом столбце. Вы можете выполнять эту операцию произвольное (ноль или более) количество раз. Вы можете применять эту операцию для одного столбца произвольное количество раз.
После того, как вы закончили, вы вычисляете для каждой строки наибольший элемент в ней. Предположим, для \(i\)-й строки он равен \(r_i\). Чему равно наибольшее значение \(r_1+r_2+\ldots+r_n\)?
Выходные данные
Выведите \(t\) целых чисел: ответы на все наборы входных данных, в порядке, в котором они заданы в тесте.
Примечание
В первом тестовом наборе можно сдвинуть третий столбец вниз на один, тогда будет \(r_1 = 5\) и \(r_2 = 7\).
Во втором тестовом наборе можно ничего не делать, тогда будет \(r_1 = r_2 = 10\) и \(r_3 = 9\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
2 3
2 5 7
4 2 4
3 6
4 1 5 2 10 4
8 6 6 4 9 10
5 4 9 5 8 7
3 3
9 9 9
1 1 1
1 1 1
|
12
29
27
|