这是问题的更难版本。区别仅在于约束条件。
给你一个矩形 $$$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
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$$$。