CF1209E2.Rotate Columns (hard version)

This is a harder version of the problem. The difference is only in constraints.

You are given a rectangular $n \times m$ matrix $a$. In one move you can choose any column and cyclically shift elements in this column. You can perform this operation as many times as you want (possibly zero). You can perform this operation to a column multiple times.

After you are done with cyclical shifts, you compute for every row the maximal value in it. Suppose that for $i$-th row it is equal $r_i$. What is the maximal possible value of $r_1+r_2+\ldots+r_n$?

这是一个更难版本的问题，区别仅在于约束条件。

给你一个 $n \times m$ 的矩形矩阵 $a$。在一次操作中，你可以任选一列，并对该列元素进行循环移位（cyclic shift）。该操作可执行任意多次（包括零次），且可对同一列执行多次。

完成所有循环移位操作后，你将对每一行计算其最大值。设第 $i$ 行的最大值为 $r_i$。那么 $r_1 + r_2 + \ldots + r_n$ 的最大可能值是多少？

The first line contains an integer $t$ ($1 \le t \le 40$), the number of test cases in the input.

The first line of each test case contains integers $n$ and $m$ ($1 \le n \le 12$, $1 \le m \le 2000$) — the number of rows and the number of columns in the given matrix $a$.

Each of the following $n$ lines contains $m$ integers, the elements of $a$ ($1 \le a_{i, j} \le 10^5$).

第一行包含一个整数 $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$）。

Print $t$ integers: answers for all test cases in the order they are given in the input.

输出 $t$ 个整数：按输入中给出的顺序，输出所有测试用例的答案。

In the first test case you can shift the third column down by one, this way there will be $r_1 = 5$ and $r_2 = 7$.

In the second case you can don't rotate anything at all, this way there will be $r_1 = r_2 = 10$ and $r_3 = 9$.

在第一个测试用例中，你可以将第三列向下移动一格，这样将得到 $r_1 = 5$ 和 $r_2 = 7$。

在第二个测试用例中，你完全可以不进行任何旋转，这样将得到 $r_1 = r_2 = 10$ 且 $r_3 = 9$。