Paladyn, wojownik biegły w świętej magii, potrzebuje twojej pomocy w tworzeniu zaklęć. Jako Paladyn, każde zaklęcie musi być również palindromem, co oznacza, że czyta się je tak samo od przodu, jak i od tyłu. Koszt stworzenia nowego zaklęcia opiera się na kosztach par run (kosztach sąsiadujących liter), które występują w finalnym zaklęciu. Pary run, które nie zostały podane na wejściu, są niedozwolone w finalnym zaklęciu.

Całkowity koszt zaklęcia to suma kosztów wszystkich par run w zaklęciu, uwzględniająca każde wystąpienie danej pary. Na przykład, jeśli zaklęcie to abacaba, koszt jest sumą kosztów ab + ba + ac + ca + ab + ba.

Wyznacz najmniejszy koszt stworzenia nowego zaklęcia Paladyna o dokładnie zadanej długości.

Wejście

Pierwsza linia wejścia zawiera dwie liczby całkowite $n$ ($1 \le n \le 676$) oraz $k$ ($2 \le k \le 100$), gdzie $n$ to liczba par run, a $k$ to pożądana długość zaklęcia w runach (tj. literach).

Każda z kolejnych $n$ linii zawiera ciąg znaków $s$ ($s$ składa się z dokładnie dwóch małych liter alfabetu angielskiego, które mogą być takie same lub różne) oraz liczbę całkowitą $c$ ($1 \le c \le 100$), gdzie $s$ jest parą run, a $c$ jest kosztem tej pary. Wszystkie pary run są unikalne.

Wyjście

Wypisz pojedynczą liczbę całkowitą, która jest najmniejszym możliwym kosztem skonstruowania zaklęcia o długości $k$ z podanych run, lub $-1$, jeśli nie jest to możliwe.

Przykład

Wejście 1

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

Wyjście 1

20