Hablemos del gran elefante de la habitación 1: hace tiempo que tienes un canguro en tu habitación y necesitas esconderlo sin levantar sospechas, ya que quieres quedarte con el animal. Esconder un animal de este tamaño es difícil:

Si utilizas mucho espacio, es obvio que estás ocultando algo a tus amigos. Por lo tanto, es conveniente utilizar el menor espacio posible para esconder el canguro.

Cuando el canguro está colocado contra la pared, haces una foto en blanco y negro del animal. Al buscar en la casa, los únicos utensilios que encontraste para esconder el canguro fueron latas vacías.

Las dimensiones de las latas se corresponden con ~2~ \(×\) ~2~ píxeles en la imagen y estas latas no pueden superponerse. Por lo tanto, puedes hacer un canguro y si alguien te pregunta por qué tienes latas en forma de de un canguro, simplemente dices que es una broma pesada tuya.

La posición de cada lata tiene que corresponder exactamente a un bloque de ~2~ \(×\) ~2~ píxeles en la imagen, y no se pueden desplazar o girar para cubrir sólo parcialmente algunos píxeles. Además, las latas no pueden flotar en el aire, por lo que cada lata tiene que estar apoyada en el suelo, que está justo debajo de la fila inferior de la imagen, o por otra lata, para lo cual al menos una de las mitades izquierda y derecha debe apoyarse directamente en otra lata. Por lo demás, la estructura no necesita estar equilibrada.

Tarea

¿Cuál es el número mínimo de latas necesario para ocultar el canguro?

Entrada

La entrada consiste en:

• Una línea que contiene dos enteros ~n~ ~(2 \le n \le 100)~ y ~m~ ~(2 \le m \le 10)~, la altura y anchura de tu habitación. Tanto ~n~ como ~m~ son pares.
• ~n~ líneas, cada una de las cuales contiene ~m~ caracteres que son '.' o '#', donde '#' marca una posición que debe ser ocultada por una lata.

Salida

Se obtiene el número mínimo de latas de \(2 × 2\) necesarias para ocultar el canguro en la habitación.

Ejemplo de Entrada #1

4 4
....
..#.
.##.
##..

Ejemplo de Salida #1

3

Ejemplo de Entrada #2

4 4
#.#.
....
#...
....

Ejemplo de Salida #1

4

Ejemplo de Entrada #1

14 8
........
....##..
...###..
....##..
.....#..
...####.
..#####.
.######.
.#####..
.###....
.##.....
..##....
...#....
.###....

Ejemplo de Salida #1

15