给您一个矩形网格,其中包含 $$$n$$$ 行和 $$$m$$$ 列。位于从顶部起第 $$$i$$$ 行和从左侧起第 $$$j$$$ 列的单元格中写入了值 $$$a_{ij}$$$。
您可以执行以下操作任意次数(可能为零):
- 选择任意两个相邻的单元格并将其中的值乘以 $$$-1$$$。如果两个单元共用一条边,则称为相邻单元。
请注意,您可以在不同的操作中多次使用一个单元格。
您对 $$$X$$$ 感兴趣,即网格中所有数字的总和。
通过这些操作您可以实现的最大 $$$X$$$ 是多少?
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 100$$$)。测试用例的描述如下。
每个测试用例的第一行包含两个整数 $$$n$$$,$$$m$$$ ($$$2 \le n$$$, $$$m \le 10$$$)。
以下 $$$n$$$ 行每行包含 $$$m$$$ 个整数,第 $$$i$$$ 行中的第 $$$j$$$ 元素为 $$$a_{ij}$$$ ($$$-100\leq a_{ij}\le 100$$$)。
输出
对于每个测试用例,打印一个整数 $$$X$$$,即根据需要多次应用操作后网格中所有值的最大可能总和。
示例
输入 #1
2 2 2 -1 1 1 1 3 4 0 -1 -2 -3 -1 -2 -3 -4 -2 -3 -4 -5
输出 #1
2 30
注意
在第一个测试用例中,总是至少有一个$$$-1$$$,所以答案是$$$2$$$。
在第二个测试用例中,我们可以对水平相邻的元素使用六次运算,并使所有数字都为非负数。所以答案是:$$$2\times 1 + 3\times2 + 3\times 3 + 2\times 4 + 1\times 5 = 30$$$。