测试数据来自 nnu_contest/1264

矩阵取数（Easy Version）

时间限制:1s

空间限制:64MB

题目描述

给定正整数\(n,m\)，在\(n*m\)的矩阵中取若干个数字，但任意两个取出的数字在矩阵中的位置不能相邻。

（若A位置与B位置在矩阵的同一行，但列号相差1，或它们在同一列，但行号相差1，则称它们相邻。

注意：左上方、左下方、右上方、右下方不算相邻。）

问：取出数字的最大和是多少？

输入格式

第一行两个整数\(n,m\)，表示矩阵大小。

接下来\(n\)行每行\(m\)个整数，表示这个矩阵

输出格式

一个整数，表示答案。

样例输入1

3 3
1 3 5
2 4 1
2 3 5

样例输出1

17

样例1解释

选第一行1,5,第二行4,第三行2,5

可以证明这是最大的情况。

样例输入2

3 3
10 7 6
4 15 2
3 33 1

样例输出2

49

样例2解释

10+6+33=49

样例输入3

5 5
1 4 12 7 2
9 23 1 4 11
12 3 7 2 7
92 15 44 3 1
10 7 8 2 20

样例输出3

212

样例输入4

6 2
8 3 
8 2 
8 1 
6 5 
2 10 
2 9 

样例输出4

34

数据范围及限制

\(1\le n,m\le 6\)

\(0<a_{ij}<10^4\)