성스러운 마법에 능숙한 전사인 팔라딘은 주문을 구성하는 데 당신의 도움이 필요합니다. 팔라딘의 모든 주문은 팰린드롬(Palindrome)이어야 합니다. 즉, 앞에서 읽을 때와 뒤에서 읽을 때가 같은 문자열이어야 합니다. 새로운 주문을 구성하는 비용은 최종 주문에 나타나는 룬 쌍(인접한 두 글자의 비용)을 기반으로 합니다. 입력으로 주어지지 않은 룬 쌍은 최종 주문에 사용할 수 없습니다.

주문의 총 비용은 주문 내에서 각 룬 쌍이 나타날 때마다 해당 룬 쌍의 비용을 모두 합한 값입니다. 예를 들어, 주문이 abacaba라면 비용은 ab + ba + ac + ca + ab + ba의 합입니다.

정확히 주어진 길이의 새로운 팔라딘 주문을 만드는 최소 비용을 구하세요.

입력

첫 번째 줄에는 두 정수 $n$ ($1 \le n \le 676$)과 $k$ ($2 \le k \le 100$)가 주어집니다. 여기서 $n$은 룬 쌍의 개수이고, $k$는 원하는 주문의 길이(글자 수)입니다.

다음 $n$개의 줄에는 각각 문자열 $s$ ($s$는 정확히 두 개의 소문자로 구성되며, 같거나 다를 수 있음)와 정수 $c$ ($1 \le c \le 100$)가 주어집니다. 여기서 $s$는 룬 쌍이고, $c$는 해당 룬 쌍의 비용입니다. 모든 룬 쌍은 서로 다릅니다.

출력

주어진 룬을 사용하여 길이 $k$의 주문을 구성하는 최소 비용을 출력하세요. 만약 불가능하다면 $-1$을 출력하세요.

예제

입력 1

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

출력 1

20