Problem 2051. -- Big Boss

2051: Big Boss

Time Limit: 3 Sec  Memory Limit: 256 MB   64bit IO Format: %lld
Submitted: 35  Accepted: 9
[Submit][Status][Web Board]

Description

Big Boss是一名十分强大的士兵,甚至用“全世界最伟大的战士”来称呼他都不为过分,Big Boss不仅拥有超强的战斗技巧,他的战斗意识也是十分的过人。因此他创造了不少堪称传说的战斗记录,甚至在“食蛇者作战”中以一己之力避免了美苏全面冷战。但是Big Boss意识到仅靠自己能做到的事情是很有限的,于是他决定成立一个武装组织来实现自己的理念。

在召集了自己的好朋友OcelotKaz Miller之后,Big Boss决定在南非某个偏远地区成立自己的组织Outer Heaven。由于在之前的“食蛇者作战”中Big Boss夺取了“哲学家的遗产”,所以钱和一般的人力对于他来说不再是问题,这个时候他需要考虑的就是如何获得精锐的士兵和新锐的武器装备。

OcelotBig Boss出了个主意,让Big Boss到战场上去回收士兵和装备。因为以Big Boss的身手和他们开发的“富尔顿气球”装置,他们一定能够安全的回收人员和物资,而且没有哪个士兵在听到Big Boss的大名后会拒绝加入,因为Big Boss就是全世界士兵的偶像。

Kaz Miller进行了情报工作后,Big Boss得知了战区的全部资料。我们可以认为战区就是一个n*m的矩形地区。每一个地区都有一名精锐士兵驻守(用1表示)或者存放一件新锐武器装备(用0表示)。Big Boss会选择从最安全的左上角(也就是坐标(1,1)点)进入战区,他每到一个点都一定能回收这个点的士兵或者武器装备。但是出于安全考虑,他前进的方向只能是向下或者是向右,直到在某个点结束并搭乘直升机返回。

一个精锐士兵和一件武器装备能组成一个精英战斗小组,当然战斗小组越多对组织越有利,仅仅是人多或者装备多并没有什么意义。所以Big Boss希望在这一次行动后能组成最多的战斗小组。为了预测行动收益,Kaz Miller交给了你一个任务,那就是计算出最优方案下这次行动后能够组成多少个战斗小组。

Input

多组数据

第一行包含两个整数n,m,表示地图的尺寸大小。

接下来的n行中每行包含m个整数,表示地图中每一点的信息

Output

仅包含一个整数,输出最优方案下能组成的战斗小组数量

Sample Input

4 2
1 1
0 0
1 1
1 0

Sample Output

2

HINT


1<=n,m<=50

Author

ghdny2015

[Submit][Status][Web Board]