Найкращий гребінець

Після опанування викликів зі знаходження найбільших квадратів та прямокутників із нулів у числовій матриці, з'явилася нова, більш узагальнена задача. Дано матрицю, що складається з нулів та одиниць, потрібно знайти оптимальний "гребінець", який можна побудувати із нульових клітинок у цій матриці. Оптимальним гребінцем називається такий, що покриває максимальну кількість клітинок у матриці. Ланкою гребінця є непорожній прямокутний фрагмент, що складається лише з нульових елементів матриці, тобто підматриця з площею більшою за нуль, що містить лише нулі. $k$-гребінець — це структура, утворена вертикальним з'єднанням $k$ (0 \leq k \leq m) ланок. У цих ланках ліва $x$-координата має бути однаковою, сусідні ланки повинні відрізнятися за шириною, а всі ланки разом утворювати зв'язну фігуру. $0$-гребінець завжди існує та має розмір $0$.

Ілюстрація на Рисунку $\text{1}$ зображує валідний $7$-гребінець. Хоча структура займає $8$ рядків, це саме $7$-гребінець, оскільки другий та третій рядки знизу належать одній і тій же ланці (сусідні ланки повинні відрізнятися шириною, але ланка може охоплювати більше ніж $1$ рядок). Структура на Рисунку $\text{2}$ не є валідним гребінцем, оскільки ліві $x$-координати ланок не збігаються. Аналогічно, структура на Рисунку $\text{3}$ не є валідним гребінцем, оскільки не є зв'язною. Варто відзначити, що оптимальний прямокутник еквівалентний найкращому $1$-гребінцю (гребінець з висотою $1$ ланка). Очевидно, що для кожної довжини $k$ у матриці можна або знайти найкращий гребінець, або зробити висновок про його відсутність (тобто найкращий гребінець має розмір $0$). Наприклад, на Рисунку $\text{4}$ підсвічено найкращий $3$-гребінець (ненульові елементи матриці позначено $\text{X}$).

Рис. 4

Ваша задача — визначити розмір найбільшого гребінця серед усіх $k$-гребінців, які можна побудувати на нульових клітинках заданої матриці (для усіх $k$ від $0$ до $m$).