E2. Вращая столбцы (усложнённая версия)
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это сложная версия задачи, отличающаяся более высокими ограничениями.

Вам дана прямоугольная матрица $$$a$$$ размером $$$n \times m$$$. За один ход вы можете выбрать произвольный столбец и циклически сдвинуть все элементы в этом столбце. Вы можете выполнять эту операцию произвольное (ноль или более) количество раз. Вы можете применять эту операцию для одного столбца произвольное количество раз.

После того, как вы закончили, вы вычисляете для каждой строки наибольший элемент в ней. Предположим, для $$$i$$$-й строки он равен $$$r_i$$$. Чему равно наибольшее значение $$$r_1+r_2+\ldots+r_n$$$?

Входные данные

Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 40$$$), количество наборов входных данных в тесте.

Первая строка каждого набора входных данных содержит целые числа $$$n$$$ и $$$m$$$ ($$$1 \le n \le 12$$$, $$$1 \le m \le 2000$$$) — число строк и число столбцов в матрице $$$a$$$.

Каждая из следующих $$$n$$$ строк содержит $$$m$$$ чисел — элементы матрицы $$$a$$$ ($$$1 \le a_{i, j} \le 10^5$$$).

Выходные данные

Выведите $$$t$$$ целых чисел: ответы на все наборы входных данных, в порядке, в котором они заданы в тесте.

Пример
Входные данные
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
Примечание

В первом тестовом наборе можно сдвинуть третий столбец вниз на один, тогда будет $$$r_1 = 5$$$ и $$$r_2 = 7$$$.

Во втором тестовом наборе можно ничего не делать, тогда будет $$$r_1 = r_2 = 10$$$ и $$$r_3 = 9$$$.