题目描述

给定一个有 $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\times 1 + 3\times2 + 3\times 3 + 2\times 4 + 1\times 5 = 30$。

由 ChatGPT 4.1 翻译

样例

2
2 2
-1 1
1 1
3 4
0 -1 -2 -3
-1 -2 -3 -4
-2 -3 -4 -5

2
30