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