矩阵取数（Hard Version）

时间限制:3s

空间限制:64MB

题目描述

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

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

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

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

输入格式

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

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

输出格式

一个整数，表示答案。

样例输入1

5 4
9 41 33 8 
50 12 33 49 
28 26 44 42 
29 41 40 11 
16 1 46 20 

样例输出1

298

样例输入2

9 9
30 13 12 50 9 23 29 11 31 
2 36 4 40 14 15 46 50 1 
12 18 13 45 41 37 33 47 43 
29 21 28 50 15 3 38 45 49 
5 46 10 22 4 49 28 26 33 
1 2 28 22 50 17 15 7 1 
8 30 46 2 48 34 44 31 34 
24 15 48 16 4 21 12 1 22 
49 2 37 10 21 50 10 32 8 

样例输出2

1080

数据范围及限制

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

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