CF1447B.Numbers Box

You are given a rectangular grid with $n$ rows and $m$ columns. The cell located on the $i$-th row from the top and the $j$-th column from the left has a value $a_{ij}$ written in it.

You can perform the following operation any number of times (possibly zero):

• Choose any two adjacent cells and multiply the values in them by $-1$. Two cells are called adjacent if they share a side.

Note that you can use a cell more than once in different operations.

You are interested in $X$, the sum of all the numbers in the grid.

What is the maximum $X$ you can achieve with these operations?

给你一个 $n$ 行 $m$ 列的矩形网格。位于从上往下第 $i$ 行、从左往右第 $j$ 列的格子中写有一个数值 $a_{ij}$。

你可以执行以下操作任意次（包括零次）：

• 任选两个相邻的格子，并将其中的数值同时乘以 $-1$。若两个格子有一条公共边，则称它们相邻。

注意：同一个格子可在不同的操作中被多次使用。

你关心的是 $X$，即网格中所有数字的总和。

通过这些操作，你能得到的最大 $X$ 是多少？

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 100$). Description of the test cases follows.

The first line of each test case contains two integers $n$,$m$ ($2 \le n$, $m \le 10$).

The following $n$ lines contain $m$ integers each, the $j$-th element in the $i$-th line is $a_{ij}$ ($-100\leq a_{ij}\le 100$).

每个测试包含多个测试用例。第一行包含测试用例的数量 $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$）。

For each testcase, print one integer $X$, the maximum possible sum of all the values in the grid after applying the operation as many times as you want.

对于每个测试用例，输出一个整数 $X$，即在任意多次执行该操作后，网格中所有数值之和的最大可能值。

In the first test case, there will always be at least one $-1$, so the answer is $2$.

In the second test case, we can use the operation six times to elements adjacent horizontally and get all numbers to be non-negative. So the answer is: $2\times 1 + 3\times2 + 3\times 3 + 2\times 4 + 1\times 5 = 30$.

在第一个测试用例中，始终至少存在一个 $-1$，因此答案为 $2$。

在第二个测试用例中，我们可对水平相邻的元素执行六次操作，使所有数字均变为非负数。因此答案为：$2\times 1 + 3\times2 + 3\times 3 + 2\times 4 + 1\times 5 = 30$。