Пощадите эвоков!
После успешной осады Облачного города, император Палпатин, полон решимости, поручил вам начать строительство новой Имперской базы на лесной луне Эндор. Однако Эндор является домом для милых существ, известных как 'эвоки'.
Палпатин, испытывая слабость к этим эвокам в своем иначе бессердечном сердце, приказал, чтобы ни одно из существующих жилищ эвоков не было нарушено. Более того, он попросил, чтобы база имела как можно большую общую площадь, которую можно разделить на три прямоугольных здания. Помогите Палпатину в его стремлении к межгалактическому господству!
Вам предоставлена карта Эндора в виде прямоугольной сетки размером m×n, где некоторые ячейки отмечены как жилища эвоков, а другие ячейки пусты. Ваша задача — разместить до трех (но, возможно, меньше) прямоугольных зданий на этой сетке так, чтобы здания не перекрывались друг с другом и не занимали ячейки с жилищами эвоков.
Входные данные
Входные данные содержат несколько тестов. Каждый тест начинается с одной строки, содержащей пару целых чисел m и n (где 1 ≤ m ≤ 250 и 1 ≤ n ≤ 250), представляющих количество строк и столбцов в сетке. Следующие m строк задают карту Эндора; каждая строка содержит n символов, где каждый символ — это либо '.' (точка), обозначающая пустое пространство, либо 'e' (строчная E) для жилища эвока. После последнего теста будет одна строка, содержащая "0 0"; эту строку обрабатывать не следует.
Выходные данные
Для каждого теста на входе выведите одно целое число, указывающее максимальную площадь, которую могут покрыть здания.