Найкращий гребінець
Після того, як задачі знаходженея у числовій матриці найбільших квадратів та прямокутників з нулів стали стандартними, з'явилась нова задача, яка узагальнює усі попередні. Задано матрицю з нулів та одиниць. Необхідно знайти найкращий "гребінець"', який можна побудувати на нульових комірках цієї матриці (найкращим називається гребінець, який займає найбільшу кількість комірок заданої матриці). Ланкою гребінця називається непорожня прямокутна область з нулів у матриці, тобтоь деяка підматриця ненульової площі, яка складається лише з нулів. k-гребінцем називається фігура, яка отримується з'єднанням по вертикалі k (0 ≤ k ≤ m) ланок. В усіх ланках повинна співпадати x-координата лівої сторони, сусідні ланки повинні мати різну ширину, а усі ланки разом повинні утворвати цілісну фігуру, тобто повинні бути зв'язними. При цьому 0-гребінець існує завжди і має розмір 0.
Фігура на рисунку 1 є правильним 7-гребінцем. Хоча фігура займає 8 рядків, вона є 7-гребінцем, так як на другому і третьому знизу рядках знаходиться одна і та ж ланка (сусідні ланки обов'язково повинні бути різної ширини, але ланка може бути висотою більше 1 рядка). Фігура на рисунку 2 не є правильним гребінцем, так як ліва x-координата ланок не спіопадає. Фігура на рисунку 3 також не є правильним гребінцем, так як не є зв'язною фігурою. Можна помітити, что найкращий прямокутник це те ж саме, що найкращий 1-гребінець (гребінець висотою в 1 ланку). Очевидно, що для кожної довжини k у матриці можна ао знайти найкращий гребінець, або оголосити, що його немає (тобто найкращий гребінець має розмір 0). Наприклад, на рисунку 4 позначено кращий 3-гребінець (знаком X позначено ненульові елементи у матриці).
Рис. 4
Ваша задача - знайти у заданій матриці найкращий гребінець серед усіх k-гребінців матриці (для усіх k від 0 до m).
Вхідні дані
У першому рядку вхідного файлу задано два цілих числа - висота (1 ≤ m ≤ 2000) та ширина (1 ≤ n ≤ 2000) матриці відповідно. Далі у m рядках задано по n чисел через пропуск - задану матрицю.
Вихідні дані
У вихідний файл необхідно вивести розмір найбільшого гребінця серед усіх k-гребінців, які можна побудувати на нульових комірках вхідної матриці.