1142: 糖果盒

内存限制:16 MB 时间限制:1.000 S
评测方式:文本比较 命题人:
提交:47 解决:19

题目描述

一个被分为 n*m 个格子的糖果盒,第 i 行第 j 列位置的格子里面有 a [ i ][ j ] 颗糖。本来 tenshi 打算送这盒糖果给某 PPMM 的,但是就在要送出糖果盒的前一天晚上,一只极其可恶的老鼠夜袭糖果盒,有部分格子被洗劫并且穿了洞。tenshi 必须尽快从这个糖果盒里面切割出一个矩形糖果盒,新的糖果盒不能有洞,并且 tenshi 希望保留在新糖果盒内的糖的总数尽量多。


任 务 :
请帮tenshi设计一个程序 计算一下新糖果盒最多能够保留多少糖果。

输入

第一行有两个整数 n、m。
第 i + 1 行的第 j 个数表示 a [ i ][ j ],如果这个数为 0 ,则表示这个位置的格子被洗劫过。
其中:
1 ≤ n,m ≤ 1000
0 ≤ a [ i ][ j ]≤ 255

注意:本题提供 16 MB 内存,时间限制为2秒。

 

输出

输出最大糖果数

样例输入 复制

3 4
1  2  3  4
5  0  6  3
10 3  4  0

样例输出 复制

17