方格取数问题

题目描述

有一个 $m$ 行 $n$ 列的方格图,每个方格中都有一个正整数。现要从方格中取数,使任意两个数所在方格没有公共边,且取出的数的总和最大,请求出最大的和。

输入输出格式

输入格式


第一行是两个用空格隔开的整数,分别代表方格图的行数 $m$ 和列数 $n$。 第 $2$ 到第 $(m + 1)$ 行,每行 $n$ 个整数,第 $(i + 1)$ 行的第 $j$ 个整数代表方格图第 $i$ 行第 $j$ 列的的方格中的数字 $a_{i, j}$。

输出格式


输出一行一个整数,代表和最大是多少。

输入输出样例

输入样例 #1

3 3
1 2 3
3 2 3
2 3 1 

输出样例 #1

11

说明

**数据规模与约定** 对于 $100\%$ 的数据,保证 $1 \leq n, m \leq 100$,$1 \leq a_{i, j} \leq 10^5$。 **提示** 请注意输入的第一行先读入 $m$ 再读入 $n$。