Władze miasta Zagrzebia zdecydowały o budowie nowego parkingu. W tym celu wykorzystają teren o prostokątnym kształcie, który możemy wyobrazić sobie jako macierz o $N$ wierszach i $M$ kolumnach. Aby przyciągnąć gości i tym samym zwiększyć dochody, burmistrz postanowił umieścić na wybranych polach terenu fontanny, studnie i inne elementy dekoracyjne. Pozostałe pola są przeznaczone do ruchu pojazdów i zostaną przekształcone w jedną z dwóch możliwości: miejsca parkingowe lub pola do swobodnego poruszania się pojazdów.

Pojazdy mogą poruszać się po parkingu, przemieszczając się w każdym kroku na sąsiednie pole w jednym z czterech kierunków (północ, południe, wschód lub zachód). Parking musi być zaprojektowany tak, aby w każdej chwili z każdego miejsca parkingowego można było dotrzeć do wjazdu/wyjazdu, który znajduje się w lewym górnym rogu (na przecięciu pierwszego wiersza i pierwszej kolumny). Oznacza to, że pojazdy zaparkowane na miejscach parkingowych nie mogą blokować wyjazdu innym pojazdom. Innymi słowy, każdy zaparkowany pojazd musi mieć możliwość wyjazdu z parkingu bez konieczności przesuwania innych zaparkowanych pojazdów.

Pomóż burmistrzowi i wyznacz największą możliwą liczbę miejsc parkingowych dla danego terenu.

Uwaga: Pole w pierwszym wierszu i pierwszej kolumnie jest wjazdem na parking, nie jest przeznaczone do parkowania i zawsze będzie wolne.

Wejście

W pierwszym wierszu znajdują się liczby naturalne $N$ i $M$ ($1 \le N \le 6$, $1 \le M \le 100$), oznaczające liczbę wierszy i kolumn terenu. Kolejne $N$ wierszy zawiera po $M$ znaków opisujących wygląd terenu: znakiem 'x' oznaczone jest pole, na którym zostanie zbudowana fontanna, pozostałe pola oznaczone są znakiem '.' i zostaną przekształcone na potrzeby parkingu.

Wyjście

W jedynym wierszu wypisz poszukiwaną maksymalną możliwą liczbę miejsc parkingowych.

Podzadania

Przykład

Wejście 1

3 3
...
.x.
...

Wyjście 1

2

Wejście 2

3 3
...
..x
...

Wyjście 2

4

Wejście 3

3 6
.x..x.
..x.x.
......

Wyjście 3

3

Wejście 4

4 5
....x
....x
..x..
.x..x

Wyjście 4

7

Uwagi

Wyjaśnienie czwartego przykładu: jeden z możliwych układów miejsc parkingowych:

.PPPx
....x
.Px.P
PxP.x