Задача Flat2019. “Мій дім – моя фортеця” – слоган забудовника, в якого Павло хоче придбати новеньку квартиру. Щоправда, через велику кількість доступних планувань очі розбігаються і дуже складно вибрати, а яка ж квартира краще.
Забудовник надав плани квартир у вигляді прямокутників-таблиць, поділених на M рядків та N стовпчиків. Кожна клітинка такої таблиці містить або 1 (стіна), або 0 (порожня підлога). Павло вирішив, що хоче вразити друзів розмірами своєї вітальні, а тому його ціль – отримати найбільшу за площею кімнату, зруйнувавши стіну (по суті, замінивши “1” на “0”). Забудовник не дозволяє руйнувати більш як одну стіну, а крім того, забороняє руйнувати зовнішні стіни.
Допоможіть Павлу знайти максимальну площу кімнати, яку можна отримати такими діями.
Технічні умови. Програма Flat2019 читає з пристрою стандартного введення «план квартири». Перший два рядки містять два числа M, N – висота та ширина плану квартири відповідно (3 ≤ M ≤ 1000, 3 ≤ N ≤ 1000). M наступних рядків містить по N нулів або одиниць, що йдуть поспіль (без пробілів). Перший та останній рядок, а також перший та останній стовпчик плану відповідають зовнішнім стінам квартири, а тому складаються лише з одиниць. Програма виводить на пристрій стандартного виведення площу найбільшої кімнати, яка утвориться в разі видалення внутрішньої стіни квартири.
|
Введення |
Виведення |
|
6 8 11111111 10011001 10011001 11101001 10111001 11111111 |
10
|