题目描述

一位精通圣光魔法的勇士——圣骑士，需要你帮忙构造法术。作为圣骑士，每个法术都必须是 回文串，即正读反读都相同的字符串。构造一个新法术的成本由最终法术中出现的符文对（相邻字母）的成本决定。输入中未给出的符文对不允许出现在最终法术中。

一个法术的总成本等于其中每个符文对出现的次数乘以该符文对成本的总和。例如，若法术为 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$。

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

20

提示

翻译由 DeepSeek V3.2 完成