La administración de la ciudad de Zagreb ha decidido construir un nuevo estacionamiento. Para ello, utilizarán un terreno de forma rectangular que podemos imaginar como una matriz de $N$ filas y $M$ columnas. Para atraer clientes y aumentar los ingresos, el alcalde decidió colocar fuentes, pozos, grifos y otros tipos de fuentes ornamentales en campos predeterminados del terreno. Los campos restantes están destinados al movimiento de vehículos y se reorganizarán según una de las dos posibilidades:

• campos de estacionamiento, o
• campos para el libre movimiento de vehículos.

Los vehículos pueden moverse por el estacionamiento desplazándose en cada paso a un campo adyacente en una de las cuatro direcciones (norte, sur, este u oeste). El estacionamiento debe estar construido de tal manera que, en todo momento, desde cada plaza de estacionamiento se pueda llegar a la entrada/salida del estacionamiento, la cual se encuentra en la celda superior izquierda (en la intersección de la primera fila y la primera columna); es decir, que los vehículos estacionados no bloqueen la salida a otros vehículos. En otras palabras, cada vehículo estacionado debe ser capaz de salir del estacionamiento sin mover otros vehículos estacionados.

Ayude al alcalde a determinar el mayor número posible de plazas de estacionamiento para el terreno dado.

Nota: La celda en la primera fila y la primera columna es la entrada al estacionamiento, no está destinada al estacionamiento y siempre estará libre.

Entrada

En la primera línea se encuentran los números naturales $N$ y $M$ ($1 \le N \le 6$, $1 \le M \le 100$), el número de filas y columnas del terreno. Las siguientes $N$ líneas contienen $M$ caracteres que describen el diseño del terreno:

• el carácter 'x' marca el campo donde se construirá una fuente,
• los demás campos están marcados con el carácter '.' y se reorganizarán para el estacionamiento.

Salida

En la única línea, imprima el número máximo posible de plazas de estacionamiento.

Subtareas

Ejemplos

Entrada 1

3 3
...
.x.
...

Salida 1

2

Entrada 2

3 3
...
..x
...

Salida 2

4

Entrada 3

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

Salida 3

3

Entrada 4

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

Salida 4

7

Nota

Explicación del cuarto ejemplo: una posible disposición de las plazas de estacionamiento:

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