問題文

$K$ を $1$ 以上の整数とする。$K$ 個の文字'J', $K$ 個の文字'O', $K$ 個の文字'I'をこの順に並べた文字列をレベル $K$ のJOI文字列と呼ぶことにする。
友人のビバ子から文字列をもらったビ太郎は、お返しにレベル $K$ のJOI文字列を作ろうとしている。 そこでビ太郎は文字列を売っている「もじれつや」へ行くことにした。
もじれつやでは、$N$ 種類の文字列が売られている。$i$ 番目 $(1\le i\le N)$ の文字列は $C_i$ 円である。
ビ太郎はいくつかの文字列を購入し、それらを好きな順に並べた後全てを連結して文字列 $S$ を作る。このとき、同じ文字列を何個買っても良いし買わない文字列があってもよい。
ビ太郎は $S$ がレベル $K$ のJOI文字列を部分列に含むように文字列を選んで買おうとしている。このとき最小で何円かかるか求めるプログラムを作成せよ。ただし、どのようにしても条件を満たす文字列を作ることができない場合、$-1$を代わりに出力せよ。

注釈

$S$ が$T$ の部分列であるとは、$S$ が $T$ からいくつかの文字を抜き取って順序を保ったまま並べてできる文字列であるということである。
例えば"yuki" "ykd" "yukicoder" (空文字列)は"yukicoder"の部分列であるが、"a" "ike"などは部分列でない。

入力

$NK$
$S_1{C}_1$
$S_2{C}_2$
...
$S_N{C}_N$

$N,K,C_i(1\le i\le N)$は整数である。
$S_i(1\le i\le N)$は'J','O', 'I'のいずれかのみからなる文字列である。
$1\le N\le 80$
$1\le K\le {10}^5$
$0\le C_i\le {10}^9(1\le i\le N)$
$1\le |S_i|\le 80(1\le i\le N)$

出力

問題文の条件を満たす文字列 $S^{\prime }$ を作るのに必要な最小の金額を出力してください。どのようにしても条件を満たす文字列が作れない場合、"-1"を代わりに出力してください。 最後に改行してください。

サンプル

3 2
JOI 50
JJOI 30
IOI 20

70

1 2
JJJJ 1

-1

5 5
IOOOJ 28
JIJOOJIII 12
JIJOJIO 7
OIOJIOII 16
OJOJOJ 27

40