题目描述

译自 ROI 2025 Day1 T1. Лестница для участников олимпиады

在天狼星教育中心，学生们最喜欢聚集和交流的地方莫过于各式各样的楼梯。然而，信息学奥林匹克的参与者数量远远超过了其他任何教育项目的学生，现有的楼梯已无法满足需求。因此，装备部门决定利用一块特殊的模板，打造一座全新的楼梯。

这块模板是一个由 $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，表示表格中对应格子的数字。

输出格式

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

6 4
0011
1101
0111
1110
0111
0100

8

提示

样例解释：

详细子任务附加限制及分值如下表所示。其中子任务 $0$ 是样例。