Descripción

Dado un conjunto de ~n~ palabras, cada una de la misma longitud, podemos formar una estructura de árbol entre las palabras conectando pares de palabras con una arista. En concreto, debemos añadir exactamente ~n-1~ aristas y asegurarnos de que existe un único camino simple entre cada palabra.

Definimos el coste de una arista entre dos palabras como la suma de los costes entre cada par de letras correspondientes de las dos palabras. letras correspondientes de las dos palabras. Definimos el coste entre dos letras como el valor absoluto de la diferencia entre sus valores ASCII. Por ejemplo, el coste de una arista entre "CAMP" y "BEAR" sería ~1 + 4 + 12 + 2 = 19~ porque ~|'C' - 'B'| = 1~, ~|'A' - 'E'| = 4~, ~|M' - 'A'| = 12~, y ~P' - 'R'| = 2~.

He aquí una ilustración de un árbol de palabras con las palabras ~BEAM~, ~BEAR~, ~BEAT~, ~CAMP~ y ~CART~:

Finalmente, debido a que solo nos gusta conectar palabras que son "similares", nuestro objetivo es minimizar el valor del costo máximo de borde del árbol. En el ejemplo anterior, es imposible conectar las palabras en una estructura de árbol donde cada borde tiene un costo de menos de ~19~.

Tenga en cuenta que no hay restricciones en la estructura de árbol, es decir, cualquier palabra se puede enumerar como hijo de cualquier otro nodo. Por ejemplo, no tiene que ser un árbol de búsqueda binaria. La estructura debe, de por supuesto, ser un árbol y el costo es como se definió anteriormente.

Tarea

Dado un conjunto de ~n~ palabras, cada una de las cuales consta de ~k~ letras mayúsculas, de todos los árboles de palabras posibles que podrían formarse con esas palabras, determine el valor mínimo posible del costo de borde máximo.

Entrada

La primera línea de entrada contiene dos números enteros: ~n~ (~2 \le n \le 1000~), que indica el número de palabras, y ~k~ (~1 \le k \le 20~), indicando la longitud de cada una de las palabras. Cada una de las siguientes ~n~ líneas de entrada contiene una de las palabras. Se garantiza que estas palabras son distintas, constan exactamente de ~k~ letras mayúsculas, y comience en la columna uno.

Salida

Imprima el valor mínimo del costo de borde máximo sobre todos los árboles de palabras posibles para el conjunto de entrada palabras.

Ejemplos de Entrada y Salida

Entrada #1

5 4
BEAM
BEAR
BEAT
CAMP
CART

Salida #1

19

Entrada #2

6 3
BAN
BAR
BAT
CAN
CAP
CAR

Salida #2

2