Un Paladin, guerrier adepte de magie sacrée, a besoin de votre aide pour former des sorts. En tant que Paladin, chaque sort doit également être un palindrome, ce qui signifie qu'il s'agit de la même chaîne de caractères lorsqu'elle est lue de gauche à droite et de droite à gauche. Le coût de construction d'un nouveau sort est basé sur les coûts des paires de runes (coûts des lettres adjacentes) qui apparaissent dans le sort final. Les paires de runes non présentes dans l'entrée ne sont pas autorisées dans le sort final.

Le coût total d'un sort est la somme des coûts de toutes les paires de runes présentes dans le sort, pour chaque occurrence de la paire. Par exemple, si le sort est abacaba, alors le coût est la somme des coûts de ab + ba + ac + ca + ab + ba.

Déterminez le coût minimal pour créer un nouveau sort de Paladin d'une longueur donnée.

Entrée

La première ligne de l'entrée contient deux entiers $n$ ($1 \le n \le 676$) et $k$ ($2 \le k \le 100$), où $n$ est le nombre de paires de runes et $k$ est la longueur souhaitée du sort en runes (c'est-à-dire en lettres).

Chacune des $n$ lignes suivantes contient une chaîne $s$ ($s$ est composée exactement de deux lettres minuscules, qui peuvent être identiques ou différentes) et un entier $c$ ($1 \le c \le 100$), où la chaîne $s$ est une paire de runes et $c$ est le coût de cette paire de runes. Toutes les paires de runes sont distinctes.

Sortie

Affichez un seul entier, qui est le coût minimal possible pour construire un sort de longueur $k$ à partir des runes données, ou $-1$ si cela n'est pas possible.

Exemples

Entrée 1

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

Sortie 1

20