1288: 取数游戏

Memory Limit:128 MB Time Limit:1.000 S
Judge Style:Text Compare Creator:
Submit:7 Solved:3

Description

现在有一个$N × M$的由非负整数构成的数字矩阵,需要在其中取出若干个数字,使得取出的任意两个数字不相邻(若一个数字在另外一个数字相邻$8$个格子中的一个即认为这两个数字相邻),求取出数字和最大是多少。

Input

第一行输入整数$N$和$M$,代表矩阵有$N$行$M$列;
接下来的$N$行,每行有$M$个正整数,数据以空格分开,代表数字矩阵。

Output

一行,输出最大的和。

Sample Input Copy

2 3
87 70 85
10 3 17

Sample Output Copy

172

HINT

$2 ≤ N, M ≤ 6$,$1 ≤ 矩阵中的数据 ≤ 1000$

Source/Category