[AHOI2007] 石块地板
题目描述
小可可来到了宫殿的正厅中。大厅的地面是由一块块大小一致的正方形石块组成的,这些石块分为黑、白两色,组成了一个 $m×n$ 的矩形,在其中一个石块的下面就是通往藏宝库的通道。小可可不可能一个一个石块的尝试,因为有些石块安装了机关,一碰就会触发,整个宫殿也随之倒塌。根据藏宝图记载,通道在某一特定的区域中,这个区域是一个由数个石块组成的面积不为 $0$ 的小矩形,它的四条边与大厅地面的边平行。如果对整个大厅地面任意划分矩形,那么在所有矩形中,这个区域的黑色石块数目减去白色石块数目所得的差是最大的。
小可可希望和你分工,由他来选择区域,你来计算黑、白两色石块的数目差 $S$ 。这样就能快速而准确的确认通道所在的区域。藏宝图上说这个区域中的石块都没有安装机关,只要确定了区域,就一定能找到通道。宝藏就在眼前了,加油吧!
(假设用 $1$ 表示黑色石块,用 $0$ 表示白色石块)
输入输出格式
输入格式
输入文件的第一行为两个整数 $m,n$。
以下 $m$ 行,每行 $n$ 个字符,每个字符都是 $0$ 或 $1$。
输出格式
输出文件仅一个数,表示所有可能的区域中 $S$ 值(见前文描述)最大的一个,输出这个值即可。
输入输出样例
输入样例 #1
3 4
1011
1111
1111
输出样例 #1
10
输入样例 #2
4 5
10110
01111
11110
10101
输出样例 #2
8
说明
对于 $ 50\%$ 的数据:$1 \le m, n \leq200$。
对于 $100\%$ 的数据:$1 \le m, n \leq400$。