1065. 糖果盒

单点时限: 3.0 sec

内存限制: 256 MB

一个被分为 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

输出格式

输出最大糖果数到标准输出。

样例

Input
3 4
1 2 3 4
5 0 6 3
10 3 4 0
Output
17

41 人解决,56 人已尝试。

76 份提交通过,共有 216 份提交。

4.3 EMB 奖励。

创建: 18 年前.

修改: 7 年,3 月前.

最后提交: 4 月,1 周前.

来源: OIBH模拟赛1,提高组

题目标签