Một Paladin, một chiến binh thông thạo phép thuật thánh, cần sự giúp đỡ của bạn để tạo ra các câu thần chú. Là một Paladin, mọi câu thần chú đều phải là một Palindrome, nghĩa là nó là cùng một chuỗi khi đọc xuôi và đọc ngược. Chi phí để tạo ra một câu thần chú mới dựa trên chi phí của các cặp rune (chi phí của các chữ cái liền kề) xuất hiện trong câu thần chú cuối cùng. Các cặp rune không có trong dữ liệu đầu vào sẽ không được phép xuất hiện trong câu thần chú cuối cùng.

Tổng chi phí của một câu thần chú là tổng chi phí của tất cả các cặp rune trong câu thần chú đó cho mỗi lần cặp đó xuất hiện. Ví dụ, nếu câu thần chú là abacaba, thì chi phí là tổng của các chi phí ab + ba + ac + ca + ab + ba.

Hãy xác định chi phí nhỏ nhất để tạo ra một câu thần chú Paladin mới có độ dài chính xác bằng một giá trị cho trước.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào chứa hai số nguyên $n$ ($1 \le n \le 676$) và $k$ ($2 \le k \le 100$), trong đó $n$ là số lượng cặp rune và $k$ là độ dài mong muốn của câu thần chú (tính bằng số lượng chữ cái).

Mỗi dòng trong số $n$ dòng tiếp theo chứa một chuỗi $s$ ($s$ bao gồm chính xác hai chữ cái thường, có thể giống hoặc khác nhau) và một số nguyên $c$ ($1 \le c \le 100$), trong đó chuỗi $s$ là một cặp rune và $c$ là chi phí của cặp rune đó. Tất cả các cặp rune là phân biệt.

Dữ liệu ra

In ra một số nguyên duy nhất là chi phí nhỏ nhất có thể để xây dựng một câu thần chú có độ dài $k$ từ các rune đã cho, hoặc $-1$ nếu không thể thực hiện được.

Ví dụ

Dữ liệu vào 1

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

Dữ liệu ra 1

20