聖なる魔法に精通した戦士であるパラディンは、呪文を唱えるためにあなたの助けを必要としています。パラディンの呪文はすべて回文（Palindrome）でなければなりません。つまり、前から読んでも後ろから読んでも同じ文字列である必要があります。新しい呪文を構築するコストは、最終的な呪文の中に現れるルーンペア（隣接する文字のペア）のコストに基づきます。入力に含まれていないルーンペアを最終的な呪文に使用することはできません。

呪文の合計コストは、呪文の中に現れるすべてのルーンペアのコストの総和です。例えば、呪文が abacaba である場合、コストは ab + ba + ac + ca + ab + ba のコストの合計となります。

指定された長さの新しいパラディンの呪文を作成するための最小コストを求めてください。

入力

入力の最初の行には、2つの整数 $n$ ($1 \le n \le 676$) と $k$ ($2 \le k \le 100$) が含まれます。ここで、$n$ はルーンペアの数、$k$ は目的の呪文の長さ（文字数）です。

続く $n$ 行のそれぞれには、文字列 $s$（$s$ はちょうど2つの小文字からなり、同じ文字でも異なる文字でもよい）と整数 $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