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 \leq n \leq 50, 1 \leq m \leq 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.