圣骑士（Paladin）是一位精通神圣魔法的战士，他需要你的帮助来构建咒语。作为一名圣骑士，每一个咒语都必须是一个回文串，这意味着咒语正读和反读都是一样的。构建新咒语的代价基于咒语中出现的符文对（相邻字母）的代价。输入中未给出的符文对不允许出现在最终的咒语中。

咒语的总代价是咒语中所有符文对代价的总和，每出现一次符文对就计算一次其代价。例如，如果咒语是 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