#include "bits/stdc++.h" using namespace std; #define int long long #define REP(i, n) for (int i = 0; i < (int)n; ++i) #define RREP(i, n) for (int i = (int)n - 1; i >= 0; --i) #define FOR(i, s, n) for (int i = s; i < (int)n; ++i) #define RFOR(i, s, n) for (int i = (int)n - 1; i >= s; --i) #define ALL(a) a.begin(), a.end() #define IN(a, x, b) (a <= x && x < b) templateinline void out(T t){cout << t << "\n";} templateinline void out(T t,Ts... ts){cout << t << " ";out(ts...);} templateinline bool CHMIN(T&a,T b){if(a > b){a = b;return true;}return false;} templateinline bool CHMAX(T&a,T b){if(a < b){a = b;return true;}return false;} constexpr int INF = 1e18; signed main(){ int N,K; cin >> N >> K; vector>v(N); int ans = INF; REP(i,N){ string s; int c; cin >> s >> c; v[i] = {s,c}; int J = 0,O = 0,I = 0; REP(j,s.size()){ if(s[j] == 'J')++J; if(J >= K && s[j] == 'O')++O; if(O >= K && s[j] == 'I')++I; } if(I >= K)CHMIN(ans,c); } vectordp1(K + 100,INF); dp1[0] = 0; REP(i,N){ auto[s,c] = v[i]; int cnt = 0; REP(j,s.size()){ if(s[j] == 'J')++cnt; } REP(j,K){ CHMIN(dp1[j + cnt],dp1[j] + c); } } RREP(i,K + 99)CHMIN(dp1[i],dp1[i + 1]); vectordp2(K + 100,INF); vectordp3(K + 100,INF); dp2[0] = dp1[K]; REP(i,N){ int jj = 0,o = 0; auto[s,c] = v[i]; REP(j,s.size()){ if(s[j] == 'O')++o; } REP(j,s.size()){ if(s[j] == 'J')++jj; else if(s[j] == 'O')--o; if(K - jj >= 0){ int I = 0; if(o >= K){ FOR(k,j + 1,s.size()){ if(s[k] == 'I')++I; } CHMIN(dp3[I],dp1[K - jj] + c); } CHMIN(dp2[o],dp1[K - jj] + c); } } } REP(i,N){ auto[s,c] = v[i]; int cnt = 0; REP(j,s.size()){ if(s[j] == 'O')++cnt; } REP(j,K){ CHMIN(dp2[j + cnt],dp2[j] + c); } } RREP(i,K + 99)CHMIN(dp2[i],dp2[i + 1]); dp3[0] = dp2[K]; REP(i,N){ int o = 0,ii = 0; auto[s,c] = v[i]; REP(j,s.size()){ if(s[j] == 'I')++ii; } REP(j,s.size()){ if(s[j] == 'O')++o; else if(s[j] == 'I')--ii; if(K - o >= 0)CHMIN(dp3[ii],dp2[K - o] + c); } } REP(i,N){ auto[s,c] = v[i]; int cnt = 0; REP(j,s.size()){ if(s[j] == 'I')++cnt; } REP(j,K){ CHMIN(dp3[j + cnt],dp3[j] + c); } } RREP(i,K + 99)CHMIN(dp3[i],dp3[i + 1]); if(dp3[K] == INF)out(-1); else out(min(ans,dp3[K])); //REP(i,K + 1)out(i,dp1[i],dp2[i],dp3[i]); }