성기사

성기사는 신성 마법에 능숙한 전사로, 주문을 만드는 데 당신의 도움이 필요하다. 성기사이므로 모든 주문은 회문이어야 한다. 즉, 앞에서 읽으나 뒤에서 읽으나 같은 문자열이어야 한다. 새 주문을 만드는 비용은 최종 주문에 등장하는 룬 쌍(인접한 글자 쌍)의 비용을 바탕으로 계산한다. 입력에 주어지지 않은 룬 쌍은 최종 주문에 사용할 수 없다.

주문의 총 비용은 주문에 등장하는 각 룬 쌍의 비용을 등장 횟수만큼 더한 값이다. 예를 들어 주문이 abacaba라면 비용은 ab + ba + ac + ca + ab + ba의 비용을 모두 더한 값이다.

정확히 주어진 길이의 새 성기사 주문을 만드는 최소 비용을 구하라.

첫째 줄에 두 정수 $n$ ($1 \le n \le 676$)과 $k$ ($2 \le k \le 100$)가 주어진다. $n$은 룬 쌍의 개수이고 $k$는 만들고자 하는 주문의 길이(룬, 즉 글자 수)이다.

다음 $n$개의 줄에는 각각 문자열 $s$ (정확히 두 개의 소문자로 이루어지며, 두 글자가 같을 수도 다를 수도 있다)와 정수 $c$ ($1 \le c \le 100$)가 주어진다. $s$는 룬 쌍이고 $c$는 그 룬 쌍의 비용이다. 모든 룬 쌍은 서로 다르다.

주어진 룬으로 길이 $k$인 주문을 만드는 최소 비용을 정수 하나로 출력한다. 만들 수 없다면 $-1$을 출력한다.