聖騎士（Paladin）是一位精通神聖魔法的戰士，他需要你的協助來編寫咒語。身為聖騎士，每一道咒語都必須是迴文（Palindrome），這意味著該字串無論從前往後讀還是從後往前讀都是一樣的。建構新咒語的成本取決於最終咒語中出現的符文對（相鄰字母）的成本。輸入中未提供的符文對不允許出現在最終咒語中。

咒語的總成本是咒語中所有符文對成本的總和，且需計算每一對符文出現的次數。例如，若咒語為 abacaba，則成本為 ab + ba + ac + ca + ab + ba 的成本總和。

請計算出長度恰好為 $k$ 的新聖騎士咒語之最小成本。

輸入格式

第一行包含兩個整數 $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