시간 제한메모리 제한제출정답맞힌 사람정답 비율
0.5 초 2048 MB21111058.824%

문제

В ОЦ <<Сириус>> любимым местом для сбора и неформального общения школьников служат различные лестницы. Но количество участников олимпиады по информатике значительно превосходит количество участников любой образовательной программы, и подходящей для них лестницы среди имеющихся не нашлось, поэтому служба оснащения решила построить новую лестницу, используя специальную заготовку.

Заготовка представляет собой таблицу из $h$ строк и $w$ столбцов, пронумерованных сверху вниз и слева направо соответственно. В каждой клетке таблицы записано одно число --- ноль или единица. Лестницу можно сделать только из тех клеток таблицы, в которых записана единица.

Полученная лестница образуется из множества клеток, в которых записана единица, находящихся в нескольких последовательных строках таблицы. Множество выбранных клеток в каждой строке лестницы должно быть непрерывным отрезком. При этом в каждой следующей строке, входящей в лестницу, должно быть выбрано не меньше клеток, чем в предыдущей, находящейся непосредственно над нею, строке, а самые левые выбранные клетки в каждой строке должны располагаться в одном и том же столбце.

Ниже приведен пример лестницы.

Найдите в заданной таблице максимальное количество клеток, образующих лестницу.

입력

Первая строка входных данных содержит два целых числа $h$ и $w$ ($1 \le h, w \le 2 \cdot 10^5$, $h \cdot w \le 4 \cdot 10^6$) --- количество строк и столбцов таблицы соответственно.

Каждая из следующих $h$ строк содержит по $w$ символов, каждый из которых равен 0 или 1 --- числа, написанные в клетках таблицы.

출력

Выведите одно число --- максимальное количество клеток, образующих лестницу.

서브태스크

번호배점제한
125

$h, w \le 50$

225

$h, w \le 400$

325

$h \cdot w \le 200\,000$

425

예제 입력 1

6 4
0011
1101
0111
1110
0111
0100

예제 출력 1

8

노트

Ниже изображен рисунок для первого примера. Лестница, состоящая из максимально возможного количества клеток таблицы, отмечена серым цветом.

채점 및 기타 정보

  • 예제는 채점하지 않는다.
  • 이 문제의 채점 우선 순위는 2이다.