Descripción

Dado un mapa con ~N~ filas y ~M~ columnas. El estado de la celda en la ~i-~ésima fila (~1 \le i \le N~) y la ~j-~ésima columna (~1 \le j \le M~) está representado por un caracter ~A_{ij}~ como sigue:

• .: La celda está vacía
• o: La celda contiene un robot.
• E: La celda contiene una salida. Se asegura que en el mapa solo habrá una salida.

Eduardo está intentando salvar tantos robots como sean posibles haciendo la siguiente operación algún número de veces:

• Seleccionar una de las siguientes direcciones: arriba, abajo, izquierda, derecha. Todos los robots que aparecen en el mapa se mueven una vez en la dirección seleccionada. Cuando un robot se mueve fuera del mapa, este robot explotará y por tanto desaparecerá del mapa. En cambio, si un robot se mueve a la celda que contiene la salida, el robot será salvado e inmediatamente desaparecerá del mapa.

Ayude a encontrar el máximo número de robots que pueden ser salvados.

Entrada

La primera línea de la entrada contiene dos enteros ~N~ y ~M~ (~1 \le N, M \le 100~).

Las siguientes ~N~ líneas contienen cada una ~M~ caracteres, que representan el estado de cada celda del mapa.

Salida

Imprime el máximo número de robots que pueden ser salvados.

Subtareas

• Subtarea 1: ~1 \le N, M \le 15~ (~15~ puntos)
• Subtarea 2: Para todo par (~i, j~) se garantiza que ~A_{ij} \neq~ . (~25~ puntos)
• Subtarea 3: Sin restricciones adicionales (~60~ puntos)

Ejemplos

Entrada 1

3 3
o.o
.Eo
ooo

Salida 1

3

Seleccionando izquierda, arriba, derecha.

Entrada 2

2 2
E.
..

Salida 2

0

Entrada 3

3 4
o...
o...
oooE

Salida 3

5

Seleccionando derecha, derecha, derecha, abajo, abajo.

Entrada 4

5 11
ooo.ooo.ooo
o.o.o...o..
ooo.oE..o..
o.o.o.o.o..
o.o.ooo.ooo

Salida 4

12