409893: GYM103828 F Subgrid

Al-Aswad will give you a grid of size $$$n \times m$$$. Each cell $$$(i,j)$$$ has an integer value $$$a_{i,j}$$$.

We will consider two cells as adjacent if they have a common side.

Your task is to choose a non empty subset of adjacent cells in such a way that the sum of cells' value is as large as possible.

The first line of the input contains a single integer $$$T$$$, the number of test cases.

The first line of each test case contains two integers $$$n$$$ $$$(1 \le n \le 10^3)$$$ and $$$m$$$ $$$(1 \le m \le 9)$$$, the number of rows and the number of columns in the grid respectively.

The following $$$n$$$ lines contain $$$m$$$ integers each, the $$$j$$$-th element in the $$$i$$$-th line $$$a_{i,j}$$$ is the number written in the $$$j$$$-th cell of the $$$i$$$-th row $$$( |a_{i,j}| \le 10^5)$$$.

The sum of $$$n$$$ over all test cases doesn't exceed $$$10^3$$$.

For each test case print a single line containing one integer, the answer to the problem.

2
3 3
1 1 1
-1 -1 1
1 1 1
4 5
9 -6 -6 9 -2
6 4 -6 8 -9
8 -2 2 8 3
-6 4 6 2 5

7
72

For the first test case, You can select adjacent cells $$$(1,1), (1,2), (1,3), (2,3), (3,3), (3,2), (3,1)$$$. The sum of the values of these cells is $$$7$$$.

For the second test case, you can select all cells with positive values and the cell $$$(3,2)$$$, the sum will be: $$$27 - 2 + 47 = 72$$$. It can also be shown that this is the maximum possible sum.