No.1029 JJOOII 3

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 80
作問者 : RhoRho / テスター : ThistleThistle
9 ProblemId : 4136 / 出題時の順位表
問題文最終更新日: 2020-04-24 21:10:56

問題文

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

注釈

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

入力

$N\ K$
$S_1\ C_1$
$S_2\ C_2$
...
$S_N\ C_N$

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

出力

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

サンプル

サンプル1
入力
3 2
JOI 50
JJOI 30
IOI 20
出力
70

$2$番目の文字列を$1$つと$3$番目の文字列を$2$つ買い、その順番に結合するのが最適です。
(21:34 追記) このようにして作った文字列は"JJOIIOIIOI"となり、長さ$2$のJOI文字列を部分列に含みます。
コストは$30+20 \times 2=70$円です。

サンプル2
入力
1 2
JJJJ 1
出力
-1

サンプル3
入力
5 5
IOOOJ 28
JIJOOJIII 12
JIJOJIO 7
OIOJIOII 16
OJOJOJ 27
出力
40

$2$番目の文字列を1個と3番目の文字列を$4$個買うのが最適です。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。