P12501 「ROI 2025 Day1」奥林匹克楼梯

**译自 [ROI 2025](https://neerc.ifmo.ru/school/archive/2024-2025.html) Day1 T1.** ***[Лестница для участников олимпиады](https://neerc.ifmo.ru/school/archive/2024-2025/ru-olymp-roi-2025-day1.pdf)*** 在天狼星教育中心，学生们最喜欢聚集和交流的地方莫过于各式各样的楼梯。然而，信息学奥林匹克的参与者数量远远超过了其他任何教育项目的学生，现有的楼梯已无法满足需求。因此，装备部门决定利用一块特殊的模板，打造一座全新的楼梯。 这块模板是一个由 $h$ 行 $w$ 列组成的表格，行从上到下、列从左到右依次编号。表格的每个格子中记录了一个数字，要么是 `0`，要么是 `1`。而所谓的楼梯，只能由那些格子中填有 `1` 的格子构成。 楼梯是由若干连续行中填有 `1` 的格子集合组成的。在每一行中，被选中的格子必须形成一个连续的段。 同时，满足以下条件： - 每下一行的选中格子数量不得少于紧邻其上的上一行； - 每行中最左边的选中格子必须位于同一列。 下图展示了一个楼梯的例子：  你的任务是找出给定表格中，能够构成楼梯的最大格子数量。

输入的第一行包含两个整数 $h$ 和 $w$ $(1 \le h, w \le 2 \cdot 10^5, h \cdot w \le 4 \cdot 10^6)$，分别表示表格的行数和列数。 接下来的 $h$ 行，每行包含 $w$ 个字符，每个字符为 `0` 或 `1`，表示表格中对应格子的数字。

输出一个整数，表示能够构成楼梯的最大格子数量。

样例解释：  详细子任务附加限制及分值如下表所示。其中子任务 $0$ 是样例。 | 子任务 | 分值 | 附加限制 | | :-: | :-: | :-: | | $1$ | $25$ | $h, w \le 50$ | | $2$ | $25$ | $h, w \le 400$ | | $3$ | $25$ | $h \cdot w \le 200\,000$ | | $4$ | $25$ | 无附加限制 |