← 返回题目列表

Codeforces · 1209/E1

E1. 旋转列(简单版)

中文机器翻译题面 查看原题

这是下一个问题的简单版本。区别仅在于约束条件。

给你一个矩形 $$$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 4$$$, $$$1 \le m \le 100$$$) — 给定矩阵 $$$a$$$ 中的行数和列数。

以下 $$$n$$$ 行中的每一行都包含 $$$m$$$ 个整数,即 $$$a$$$ 的元素 ($$$1 \le a_{i, j} \le 10^5$$$)。

输出

打印 $$$t$$$ 整数:所有测试用例的答案按照输入中给出的顺序排列。

示例

输入 #1

2
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

输出 #1

12
29

注意

在第一个测试用例中,您可以将第三列向下移动一位,这样就会有 $$$r_1 = 5$$$ 和 $$$r_2 = 7$$$。

在第二种情况下,你可以根本不旋转任何东西,这样就会有 $$$r_1 = r_2 = 10$$$ 和 $$$r_3 = 9$$$。