Problem1022--淘金

1022: 淘金

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 1399  Solved: 618
[Submit] [Status] [Web Board] [Creator:]

Description

在一片n*m的土地上,每一块1*1的区域里都有一定数量的金子。这一天,你到这里来淘金,然而当地人告诉你,如果你挖了某一区域的金子,上一行,下一行,左边,右边的金子你都不能被允许挖了。那么问题来了:你最多能淘金多少?

Input

对于每组数据,第一行两个数n,m,表示土地的长和宽(1<=n,m<=200)

接下来n,每行m个数,表示每个区域的金子数量,每个区域的金子数量不超过1000

Output

对于每组数据,输出最多得到的金子数量

Sample Input

4 6
11 0 7 5 13 9
78 4 81 6 22 4
1 40 9 34 16 10
11 22 0 33 39 6

Sample Output

242