#arc0252. [arc025_2]チョコレート

[arc025_2]チョコレート

问题描述

有一个 HHWW 列的巧克力。每个方格可以是黑巧克力或白巧克力。黑巧克力和白巧克力不共享边界(也就是说,巧克力呈棋盘格纹样)。每个方格中的巧克力浓度是确定的。以下是巧克力的示例(数字表示浓度)。

妹妹从这块巧克力中切出一个矩形区域来溶化,制作巧克力奶油。妹妹对巧克力的味道十分讲究,她希望使用的黑巧克力和白巧克力的浓度之和相等(如果某种颜色的巧克力没有被使用,则将其浓度视为0)。

妹妹想知道满足条件的切割方式中,使用的巧克力方格的最大数目是多少。


输入

输入以以下格式从标准输入读取:

HH WW C1,1C_{1,1} C1,2C_{1,2} ·· C1,WC_{1,W} C2,1C_{2,1} C2,2C_{2,2} ·· C2,WC_{2,W} : CH,1C_{H,1} CH,2C_{H,2} ·· CH,WC_{H,W}

  • 第 1 行包含巧克力的行数 H(1H100)H(1≤H≤100) 和列数 W(1W100)W(1≤W≤100),用空格分隔。
  • 第 2 至 HH 行包含浓度信息。每行包含 WW 个非负整数,用空格分隔。第 ii 行第 jj 个整数 Ci,j(0Ci,j99)C_{i,j}(0≤C_{i,j}≤99) 表示以左上角为基准,第 ii 行第 jj 列方格的浓度。

输出

如果存在满足条件的切割方式,则输出其中使用的方格数的最大值;如果不存在,则输出 0。输出末尾包含换行符。


输入示例1


3 4
4 6 2 5
3 5 6 7
2 5 5 6

输出示例1


6

如下图所示,切割一个 2233 列的矩形区域,可以使方格数为 66,且浓度之和为 1717


输入示例2


2 2
4 0
7 3

输出示例2


4

注意其中包含浓度为 00 的情况。


输入示例3


2 3
0 0 0
1 2 3

输出示例3


3

输入示例4


3 3
1 2 3
6 5 4
7 8 9

输出示例4


0

在这个例子中,不存在满足条件的切割方式。


输入示例5


1 5
0 1 2 3 4

输出示例5


1

请注意,即使只切割黑巧克力或白巧克力,也可能存在满足条件的情况。