Matcom Online Grader

El alcalde ha confiado a Fito la construcción de las líneas del tren que pasará por todos los rincones de IslaGrande. Las líneas deberán construirse de forma tal que se cumplan las siguientes condiciones:

1. En las zonas no accesibles no se construirán líneas.
2. En cada zona accesible deberá construirse una única línea de tren que se conectará con exactamente dos líneas de tren ubicadas en zonas adyacentes.
3. No necesariamente se formará un único circuito para IslaGrande.

El alcalde frecuenta algunos lugares para descansar de su ardua tarea comunitaria. En estos lugares, él quiere que la línea de tren que se construya sea curva (ver ejemplo para mayor entendimiento) y Fito se debe esforzar para complacer al alcalde.

Una zona será aburrida para el alcalde si es uno de los lugares que frecuenta y se construye una línea de tren recta (no curva). Fito ahora quiere que le ayudes a determinar la cantidad mínima de zonas aburridas que pueden existir al construir las líneas del tren para IslaGrande.

Input

1ra línea : dos enteros $H$ y $W$ $(1 \le H, W \le 40)$ indicando el alto y el ancho de IslaGrande, respectivamente.
N siguientes líneas : una fila del mapa de IslaGrande. El caracter 'X' indica una zona no accesible, mientras que el caracter '.' indica las que son accesibles, excepto por las zonas que frecuenta el alcalde, que serán representados por el caracter 'A'.

Output

1ra línea : La cantidad mínima de zonas aburridas para el alcalde que se puede obtener después de construir las líneas del tren de IslaGrande, o -1 si no es posible construirlas según las condiciones a cumplir.

Sample test(s)

Hints

Hint
En el primer ejemplo, dos posibles configuraciones de líneas de tren son las siguientes:

Con color azul están señalados los lugares que frecuenta el alcalde.
En la configuración de la izquierda hay 2 lugares aburridos para el alcalde.
En la configuración de la derecha hay sólo un lugar aburrido para el alcalde.