eolymp
bolt
Try our new interface for solving problems
Problems

Лес

Лес

Time limit 1 second
Memory limit 128 MiB

В средней полосе России иногда растет лес. Для того, чтобы отделить лес от полезных пахотных земель, между лесом и полем был построен забор. Однако лес со временем растет и забор требуется перенести.

Местность можно представить в виде карты из N×M клеток. Каждая клетка содержит в себе либо лес, либо поле, либо забор. Клетки содержащие забор обладают следующими свойствами:

  1. Забор связен. Это значит, что от каждой его клетки до каждой можно дойти, передвигаясь только по соседним клеткам (соседними считаются клетки, имеющие общую сторону).

  2. Забор минимален по включению, то есть убрав какую-либо клетку из забора (заменив её на лес или поле), он перестанет быть забором.

  3. Забор разделяет лес и поле, а именно все клетки слева от забора являются лесом, все клетки справа от забора являются полем.

  4. Забор можно представить в виде последовательности клеток таким образом, что следующая клетка находится от предыдущей слева, справа или снизу.

Вам разрешается под забор использовать все клетки, которые он занимал изначально, а также клетки, находящиеся не более чем на один справа от исходных клеток забора (запрещается использовать левый и правый столбцы карты). Вашей задачей будет построить забор минимальной длины, удовлетворяющий всем вышеприведенным условиям забора. Известно, что изначальный забор является забором, а также, что левый столбец карты целиком занят лесом, а правый столбец карты целиком занят полем.

Input data

В первой строке входного файла находятся два числа N и M - размеры карты (1N, M1000). Далее следует N строк по M символов в каждой - карта, описывающая исходное положение леса, поля и забора. Клетки, занятые лесом, обозначаются символом "F", клетки, занятые полем - символом ".", клетки, занятые забором - символом "#".

Output data

Выведите единственное число - минимальную длину забора, которую можно получить.

Examples

Input example #1
5 4
FF#.
F##.
F#..
F##.
FF#.
Output example #1
5
Source 15 Международная олимпиада для школьников ЛКШ для параллелей B,A',A