Después de superar las escaleras, Laura vino a las clases. Necesitaba escribir una contraseña para comenzar sus clases. La contraseña es una cadena de longitud $n$ que satisface los siguientes requisitos:

• Hay al menos un dígito en la cadena,

• Hay al menos una letra minúscula (pequeña) del alfabeto inglés en la cadena,

• Hay al menos uno de los tres símbolos enumerados en la cadena: '#', '*', '&'.

Teniendo en cuenta que se trata de clases de programación, no es fácil escribir la contraseña.

Para cada carácter de la contraseña tenemos una cadena fija de longitud $m$; en cada una de estas $n$ cadenas hay un puntero en algún carácter. El $i-ésimo$ carácter que aparece en la pantalla es el carácter señalado en la $i-ésima$ cadena. Inicialmente, todos los punteros están en caracteres con índices $1$ en las cadenas correspondientes (todas las posiciones están numeradas a partir de $1$).

Durante una operación, Laura puede mover un puntero en una cadena de un carácter a la izquierda o a la derecha. Las cadenas son cíclicas, significa que cuando movemos el puntero que está en el carácter con índice $1$ a la izquierda, se mueve al carácter con el índice $m$, y cuando lo movemos a la derecha desde la posición $m$ se mueve a la posición $1$.

Debe determinar el número mínimo de operaciones necesarias para que la cadena que se muestre en la pantalla sea una contraseña válida.

Entrada

La primera línea contiene dos enteros $n$, $m$ $(3\le n\le 50,1\le m\le 50)$ - la longitud de la contraseña y la longitud de las cadenas que están asignadas a los símbolos de la contraseña.

Cada una de las siguientes $n$ líneas contiene la cadena que está asignada al $i-ésimo$ símbolo de la cadena de la contraseña. Su longitud es $m$, consta de dígitos, letras en minúsculas en inglés y caracteres '#', '*' o '&'.

Usted tiene tales datos de entrada que siempre puede obtener una contraseña válida.

Salida

Imprimir un número entero: el número mínimo de operaciones necesario para que la cadena, que se muestra en la pantalla, sea una contraseña válida.

Ejemplo de Entrada 1

3 4
1**2
a3*0
c4**

Ejemplo de Salida 1

1

Ejemplo de Entrada 2

5 5
#*&#*
*a1c&
&q2w*
#a3c#
*&#*&

Ejemplo de Salida 2

3

Explicación

En el caso de prueba $1$ es necesario mover el puntero de la tercera cadena a la izquierda para obtener la respuesta óptima.

En el caso de prueba $2$ uno de los posibles algoritmos será:

• Mover el puntero del segundo símbolo una vez a la derecha.

• Mover el puntero del tercer símbolo dos veces a la derecha.