2253: 长蛇阵

Memory Limit:128 MB Time Limit:1.000 S
Judge Style:Text Compare Creator:
Submit:14 Solved:2

Description

小丁是一个地道的“驴友”(特别喜欢旅游),这一天他来到了内蒙古大草原,“哇,好开阔啊!好壮观啊!”,小丁惊呼道。只见草原上许多羊在吃着肥美的嫩草。忽然,小丁大叫一声:“一字长蛇阵”,原来小丁也是一位军事爱好者,平时老爱研究一些兵器、阵法什么的。他发现了一些羊排成了“一字长蛇阵”。而且这样的阵不止一个,他想知道哪一个长蛇阵最长,最长的长蛇阵是由多少只羊连成的。小丁数了半天,眼睛都数花了。所以他想到了你,现给出小丁拍摄的卫星照片,上面记录了每只羊所处的位置,试计算最长的长蛇阵由多少只羊组成。


Input

第1行:两个整数n和m,表示草原有n行m列(0 < n m <= 1000)

第2..n+1行:每行m个整数,每个整数要么为0,要么为1。为0表示该位置没有羊存在,为1表示该位置有羊。


Output

一行:一个整数,表示最长的长蛇阵的羊的只数,找不到这样的长蛇阵则输出0。


Sample Input Copy

5 6
0 0 0 0 0 0
0 1 0 0 1 0
0 1 1 1 1 0
0 0 1 0 0 0
0 0 0 0 0 0

Sample Output Copy

4

Source/Category