CF1447B Numbers Box

给定一个有 $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 翻译