Un Paladín, un guerrero experto en magia sagrada, necesita tu ayuda para formar hechizos. Al ser un Paladín, cada hechizo debe ser también un palíndromo, lo que significa que es la misma cadena cuando se lee de adelante hacia atrás y viceversa. El costo de construir un nuevo hechizo se basa en los costos de los pares de runas (costos de letras adyacentes) que aparecen en el hechizo final. Los pares de runas que no se presentan en la entrada no están permitidos en el hechizo final.

El costo total de un hechizo es la suma de los costos de todos los pares de runas en el hechizo por cada vez que el par aparece en el mismo. Por ejemplo, si el hechizo es abacaba, entonces el costo es la suma de los costos de ab + ba + ac + ca + ab + ba.

Determina el costo más pequeño para crear un nuevo hechizo de Paladín de exactamente una longitud dada.

Entrada

La primera línea de la entrada contiene dos enteros $n$ ($1 \le n \le 676$) y $k$ ($2 \le k \le 100$), donde $n$ es el número de pares de runas y $k$ es la longitud deseada del hechizo en runas (es decir, letras).

Cada una de las siguientes $n$ líneas contiene una cadena $s$ ($s$ consiste exactamente en dos letras minúsculas, que pueden ser iguales o diferentes) y un entero $c$ ($1 \le c \le 100$), donde la cadena $s$ es un par de runas y $c$ es el costo de ese par de runas. Todos los pares de runas son distintos.

Salida

Imprime un único entero, que es el costo más pequeño posible para construir un hechizo de longitud $k$ a partir de las runas dadas, o $-1$ si no es posible.

Ejemplos

Entrada 1

5 9
ab 4
ba 1
bd 3
db 100
bc 4

Salida 1

20