Найкоротший паркан

Обмеження: 1 сек., 128 МіБ

На олімпійських іграх у Токіо завершилися змагання з кінного спорту. І поки спортсмени та спортсменки обмінюються контактами в соціальних мережах, головний конюх олімпіади має важливе завдання — прослідкувати, щоб коні не порозбігалися з місця проведення змагань і їх не довелося шукати по всьому острову Хонсю.

Поле, на якому проводяться змагання, має форму прямокутника довжиною \(l\) дзьо (одиниця вимірювання довжини) та шириною \(w\) дзьо. Конюх уже розділив поле на клітинки \(1\times1\) дзьо, які є паралельними до сторін поля. Також за допомогою дрона він знайшов місце розташування всіх коней і позначив, які клітинки зайняті кіньми. Тепер він хоче збудувати суцільний замкнений паркан, який би обгородив усіх коней на полі, щоб вони не порозбігалися. Паркан конюх будуватиме по сторонах клітинок поля.

Допоможіть йому визначити, яка мінімальна довжина паркана повинна бути, щоб обгородити всіх коней. Зверніть увагу, що паркан треба побудувати лише один, він не повинен мати самоперетинів і не повинен накладатися.

Гарантовано, що на полі принаймні одна клітинка зайнята кіньми.

Вхідні дані

У першому рядку задано два цілі числа \(l\) і \(w\) — довжину й ширину поля.

Наступні \(l\) рядків містять по \(w\) символів: \(j\)-ий символ \(i\)-ого рядка — #, якщо в клітинці \((i, j)\) є коні, і крапка(.), якщо клітинка порожня.

Вихідні дані

В одному рядку виведіть ціле число — мінімальну довжину паркана.

Обмеження

\(1 \le l, w \le 100\).

Приклади