P1123 Number Picking Game

Given an $N\times M$ matrix of non-negative integers, you need to select some numbers such that no two selected numbers are adjacent. Two numbers are considered adjacent if one is in any of the 8 neighboring cells of the other (including diagonals). Find the maximum possible sum of the selected numbers.

The first line contains a positive integer $T$, indicating there are $T$ test cases. For each test case, the first line contains two positive integers $N$ and $M$, indicating the matrix has $N$ rows and $M$ columns. The next $N$ lines each contain $M$ non-negative integers, describing the matrix.

Output $T$ lines, each containing a single non-negative integer: the required answer.

### Sample Explanation For the first test case, a valid selection is as follows: $$\begin{matrix} [67] & 75 & 63 & 10 \\ 29 & 29 & [92] & 14 \\ [21] & 68 & 71 & 56 \\ 8 & 67 & [91] & 25 \\ \end{matrix}$$ ### Constraints - For 20% of the testdata, $1\le N, M \le 3$. - For 40% of the testdata, $1\le N, M \le 4$. - For 60% of the testdata, $1\le N, M \le 5$. - For 100% of the testdata, $1\le N, M \le 6$, $1\le T \le 20$, $a_{i,j}\le 10^5$. Translated by ChatGPT 5