Збережіть евоків!#6048
Після успішної облоги Хмарного міста, Імператор Палпатін доручив вам розпочати будівництво нової Імперської бази на лісовому супутнику Ендор. Однак, Ендор є домівкою для виду милих створінь, відомих як 'Евоки'.
Маючи слабкість у своєму інакше безжальному серці до цих Евоків, Палпатін наказав, щоб жодна з існуючих домівок Евоків не була порушена. Крім того, він попросив, щоб ви зробили базу якомога більшою за загальною площею, і ця площа може бути розділена між щонайбільше трьома прямокутними будівлями. Допоможіть Палпатіну в його прагненні до міжгалактичного панування!
Для цієї задачі вам надається карта Ендору у вигляді прямокутної сітки розміром m \times n, де деякі клітинки позначені як домівки Евоків, а інші клітинки порожні. Ваша мета - розмістити до трьох (але можливо менше) прямокутних будівель на цій сітці таким чином, щоб жодні дві будівлі не перекривали одна одну, і жодна будівля не була розміщена на домівці Евоків.
Вхід міститиме декілька тестових випадків. Кожен тестовий випадок починається з одного рядка, що містить пару цілих чисел і (де 1 \le m \le 250 і 1 \le n \le 250), що представляють кількість рядків і стовпців у сітці. Наступні рядків потім визначають карту Ендору; зокрема, кожен рядок міститиме символів, де кожен символ є або '.' (крапка), що позначає порожнє місце, або 'e' (мала літера E) для домівки Евоків. Після останнього тестового випадку буде один рядок, що містить "0 0"; цей рядок не слід обробляти.
Для кожного вхідного тестового випадку виведіть одне ціле число, що вказує максимальну площу, яку можуть покрити будівлі.
Приклад 1