01子矩阵最大贡献

题目描述

Aki 有一个 $n \times m$ 的 01 矩阵 $a$（每个格子不是 $0$ 就是 $1$）。

Aki 定义任意一个子矩阵的"贡献"为：

• 设该子矩阵中 $0$ 的个数为 $c_0$，$1$ 的个数为 $c_1$；
• 贡献 $= |c_0 - c_1|$。

请你求出所有连续子矩阵中，贡献的最大值。

输入格式

第一行两个整数 $n, m$。

接下来 $n$ 行，每行一个长度为 $m$ 的 01 字符串（只由字符 0 和 1 组成），表示矩阵每一行。

输出格式

输出一个整数，表示最大贡献值。

样例 #1

样例输入 #1

2 2
11
11

样例输出 #1

4

样例解释：取整个矩阵（$2 \times 2$）作为子矩阵，此时 $c_0 = 0, c_1 = 4$，贡献为 $|0 - 4| = 4$，且这是最大值。

数据范围与提示

对于 $100\%$ 的数据，$1 \le n, m \le 12$。