Наилучшая расческа
После того, как задачи нахождения в числовой матрице наибольших квадратов и прямоугольников из нулей стали стандартными, появилась новая задача, обобщающая все предыдущие. Дана матрица из нулей и единиц. Необходимо найти наилучшую "расческу"', которую можно построить на нулевых ячейках этой матрицы (наилучшей называется расческа, которая занимает наибольшее количество ячеек данной матрицы). Звеном расчески называется непустая прямоугольная область из нулей в матрице, то есть некоторая подматрица ненулевой площади, состоящая только из нулей. 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-расчесок, которую можно построить на нулевых ячейках входной матрицы.