/*** author: yuji9511 ***/ #include using namespace std; using ll = long long; using lpair = pair; const ll MOD = 1e9+7; const ll INF = 1e18; #define rep(i,m,n) for(ll i=(m);i<(n);i++) #define rrep(i,m,n) for(ll i=(m);i>=(n);i--) #define printa(x,n) for(ll i=0;i void print(H&& h, T&&... t){cout<(t)...);} int main(){ cin.tie(0); ios::sync_with_stdio(false); ll N,K; cin >> N >> K; string S[85]; ll C[85]; rep(i,0,N) cin >> S[i] >> C[i]; ll dp[300010] = {}; rep(i,0,3*K+1) dp[i] = INF; string T = ""; T += string(K, 'J'); T += string(K, 'O'); T += string(K, 'I'); dp[0] = 0; ll cj[85] = {}, co[85] = {}, ci[85] = {}; rep(i,0,N){ for(auto &e: S[i]){ if(e == 'J') cj[i]++; else if(e == 'O') co[i]++; else ci[i]++; } } rep(i,0,3*K){ rep(j,0,N){ ll idx = i; ll cnt = 0; if(abs(K - i) <= 100 && abs(2*K - i) <= 100){ rep(k,0,S[j].size()){ if(idx >= 3*K) break; if(T[idx] == S[j][k]){ cnt++; idx++; } } }else{ if(i <= K){ cnt = cj[j]; }else if(i <= 2*K){ cnt = co[j]; }else{ cnt = ci[j]; } } dp[i+cnt] = min(dp[i+cnt], dp[i] + C[j]); } } if(dp[3*K] == INF){ print(-1); }else{ print(dp[3*K]); } }