Number Picking on a Grid

Problem Source

Network Flow 24 Problems

Problem Description

On an $m \times n$ grid board, each cell contains a positive integer.

Now you want to pick numbers from the cells so that no two picked cells share an edge (i.e. they are not adjacent), while maximizing the total sum of the numbers picked. Find that maximum sum.

Input Format

The first line contains two positive integers $m, n\ (1 \le m, n \le 30)$, the number of rows and columns of the board. The next $m$ lines each contain $n$ positive integers, the numbers in the cells; each number does not exceed $10^3$.

Output Format

Output the maximum total sum of the picked numbers.

Sample Input

3 3
1 2 3
3 2 3
2 3 1

Sample Output

11