方格取数

题目来源

网络流 24 题

在一个有 $m \times n$ 个方格的棋盘中，每个方格中有一个正整数。

现要从方格中取数，使任意两个数所在方格没有公共边，且取出的数的总和最大，求最大的和。

第一行有辆个正整数 $m, n (1\leq m, n\leq 30)$ ，分别表示棋盘的行数和列数。接下来的 $m$ 行，每行有 $n$ 个正整数，表示棋盘方格中的数，保证每个数不超过 $10^3$ 。

输出取数的最大总和。