Description

There is an $m$-row $n$-column grid, with a positive integer in each cell. You need to pick numbers from the grid so that no two chosen cells share a common edge, and the total sum of the chosen numbers is maximized. Please compute the maximum possible sum.

Input Format

The first line contains two integers separated by a space, representing the number of rows $m$ and the number of columns $n$.

From line $2$ to line $(m + 1)$, each line contains $n$ integers. The $j$-th integer on line $(i + 1)$ represents the number in the cell at row $i$, column $j$, namely $a_{i, j}$.

Output Format

Output a single integer on one line, representing the maximum sum.

3 3
1 2 3
3 2 3
2 3 1 

11

Hint

Constraints

For $100\%$ of the testdata, it is guaranteed that $1 \leq n, m \leq 100$, $1 \leq a_{i, j} \leq 10^5$.

Tip

Please note that in the first line, $m$ is read before $n$.

Translated by ChatGPT 5