题目背景

试题来源：https://koi.or.kr/archives/。中文翻译做了少量本土化修改。

按照署名—非商业性使用—相同方式共享 4.0 协议国际版进行授权。

题目描述

给定一个 $N$ 行 $M$ 列的网格图，每个格子被涂成白色或黑色。

定义以下操作为一次“V 字形涂色”：

1. 选择一个白色格子作为起点；
2. 从该格子开始，沿左上对角线（即每次向左上方移动一格）前进，直到遇到非白色格子或越出网格为止，将经过的所有格子涂为蓝色；
3. 从起点的右上方一格开始，沿右上对角线（即每次向右上方移动一格）前进，直到遇到非白色格子或越出网格为止，将经过的所有格子涂为蓝色。

现在你可以执行两次 V 字形涂色操作。请计算，两次操作之后，最多能将多少个格子涂成蓝色。

例如，在如下的 $5$ 行 $5$ 列网格中，

第一次在 $(5,5)$ 位置执行 V 字形涂色后，部分格子被涂为蓝色；

第二次在 $(5,9)$ 执行 V 字形涂色后，共有 $11$ 个格子变成蓝色。

而若先在 $(5,9)$ 执行，再在 $(5,5)$ 执行，共有 $13$ 个格子变为蓝色，这比前一种情况更多。

因此，这种情况下的答案是 $13$。

输入格式

第一行输入两个整数 $N$ 和 $M$，用空格隔开。
接下来的 $N$ 行，每行包含一个长度为 $M$ 的仅由 $0$ 和 $1$ 组成的字符串，表示网格信息。
第 $i$ 行第 $j$ 个字符为 $1$ 表示该格子为白色，为 $0$ 表示为黑色。

输出格式

输出一个整数，表示两次 V 字形涂色后最多能变成蓝色的格子数量。

5 11
10001000000
01000100000
00100110001
00010101010
00001000100

13

3 3
111
111
111

6

提示

约束条件

• $1 \leq N, M \leq 3000$
• 网格中至少存在 $2$ 个白色格子

子问题

1. （11 分）$N, M \leq 20$
2. （20 分）$N, M \leq 100$
3. （24 分）$N, M \leq 500$
4. （45 分）无附加限制条件

翻译由 ChatGPT-4o 完成