CF1209E2 Rotate Columns (hard version)

这是该问题的更难版本，区别仅在于约束条件不同。 给定一个 $n \times m$ 的矩阵 $a$。每次操作，你可以选择任意一列，并将该列的元素循环移动（即将该列的元素向下移动一格，最底部的元素移动到最顶部）。你可以对任意一列进行任意次数（包括零次）这样的操作，也可以对同一列多次操作。 完成所有循环移动后，对于每一行，计算该行中的最大值。设第 $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$ 个整数，按输入顺序分别表示每个测试用例的答案。

在第一个测试用例中，你可以将第三列向下循环移动一次，这样可以得到 $r_1 = 5$，$r_2 = 7$。 在第二个测试用例中，你可以不进行任何旋转，此时 $r_1 = r_2 = 10$，$r_3 = 9$。 由 ChatGPT 4.1 翻译