310007 - 最大不连续子序列和

在一个m×n的矩阵里,放着不同分值的宝石,收集宝石的规则是:如果取了坐标在(x,y)上的宝石,则不能取坐标在(x,y-1)(x,y+1)的宝石,并且它的上一行和下一行均不可取。例如图下所示,如果取了81这个数字,则它的左右及上下行均不可取。试问最优取法下的最大分值总和。

输入

输入有多组数据,每组数据有两个整数m,n(1≤m×n≤200000),代表矩阵的行数和列数,随后m行中,每行有n个整数,代表宝石的分值,保证宝石个数不超过1 000

输出

每组数据输出最优值。

样例

输入

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

输出

242
时间限制 1 秒
内存限制 128 MB
统计
上一题 下一题