题目描述

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

给定一个 $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$ 个整数，按输入顺序分别表示每个测试用例的答案。

输入输出样例 #1

输入 #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

输出 #1

12
29
27

说明/提示

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

在第二个测试用例中，你可以不进行任何旋转，此时 $r_1 = r_2 = 10$，$r_3 = 9$。

由 ChatGPT 4.1 翻译