You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

译自 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$ 是样例。