Problem Statement

Let $K$ be an integer greater than or equal to $1$. The string formed by arranging $K$ characters 'J', $K$ characters 'O', and $K$ characters 'I' in this order is called the JOI string of level $K$.
Bitaro, who received a string from his friend Bibako, wants to make a JOI string of level $K$ in return. So Bitaro decided to go to "Mojiretsuya", a shop that sells strings.
Mojiretsuya sells $N$ strings (there may be multiple identical strings). The $i$-th $(1 \leq i \leq N)$ string costs $C_i$ yen.
Bitaro buys some strings, arranges them in any order he likes, and then concatenates all of them to make a string $S$. Here, he may buy the same string any number of times, and there may be strings he does not buy.
Bitaro wants to choose and buy strings so that $S$ contains the JOI string of level $K$ as a subsequence. Write a program that finds the minimum cost in yen. However, if no string satisfying the condition can be made in any way, output $-1$ instead.

Notes

$S$ is a subsequence of $T$ if $S$ is a string that can be obtained by removing some characters from $T$ and arranging the remaining ones while keeping their order.
For example, "yuki" "ykd" "yukicoder" (the empty string) are subsequences of "yukicoder", but "a" "ike" and so on are not subsequences.

Input

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

$N,K,C_i (1 \leq i \leq N)$ are integers.
$S_i (1 \leq i \leq N)$ is a string consisting only of '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)$

Output

Output the minimum amount of money needed to make a string $S'$ satisfying the condition in the problem statement. If no string satisfying the condition can be made in any way, output "-1" instead. Print a newline at the end.

Sample

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