1447B.md (1735B)
1 Source: https://codeforces.com/problemset/problem/1447/B 2 3 B. Numbers Box 4 5 time limit per test 6 7 1 second 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 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. 22 23 You can perform the following operation any number of times (possibly zero): 24 25 * Choose any two adjacent cells and multiply the values in them by $-1$. Two cells are called adjacent if they share a side. 26 27 Note that you can use a cell more than once in different operations. 28 29 You are interested in $X$, the sum of all the numbers in the grid. 30 31 What is the maximum $X$ you can achieve with these operations? 32 33 Input 34 35 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. 36 37 The first line of each test case contains two integers $n$,$m$ ($2 \le n$, $m \le 10$). 38 39 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$). 40 41 Output 42 43 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. 44 45 Example 46 47 Input 48 49 ``` 50 2 51 2 2 52 -1 1 53 1 1 54 3 4 55 0 -1 -2 -3 56 -1 -2 -3 -4 57 -2 -3 -4 -5 58 ``` 59 60 Output 61 62 ``` 63 2 64 30 65 ``` 66 67 Note 68 69 In the first test case, there will always be at least one $-1$, so the answer is $2$. 70 71 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$.