#include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; const int MAX_N = 80; int counter[MAX_N][3]; int counter_sub[MAX_N][100010][3]; int main() { memset(counter, 0, sizeof(counter)); memset(counter_sub, 0, sizeof(counter_sub)); int N, K; cin >> N >> K; string S[N]; ll C[N]; for (int i = 0; i < N; ++i) { cin >> S[i] >> C[i]; } for (int i = 0; i < N; ++i) { string s = S[i]; int L = s.size(); for (int j = 0; j < L; ++j) { if (s[j] == 'J') { counter[i][0]++; } else if (s[j] == 'O') { counter[i][1]++; } else { counter[i][2]++; } for (int k = 0; k < 3; ++k) { counter_sub[i][j][k] = counter[i][k]; } } } vector dp1(K + 1, LLONG_MAX); vector dp2(K + 1, LLONG_MAX); vector dp3(K + 1, LLONG_MAX); dp1[0] = 0; for (int i = 0; i < N; ++i) { for (int j = 0; j < K; ++j) { if (dp1[j] == LLONG_MAX) continue; int nj = j + counter[i][0]; if (nj < K) { dp1[nj] = min(dp1[nj], dp1[j] + C[i]); } else { int idx = 0; while (j + counter_sub[i][idx][0] < K) { ++idx; } int o_cnt = counter[i][1] - counter_sub[i][idx][1]; dp2[o_cnt] = min(dp2[o_cnt], dp1[j] + C[i]); } } } for (int i = 0; i < N; ++i) { for (int j = 0; j < K; ++j) { if (dp2[j] == LLONG_MAX) continue; int nj = j + counter[i][1]; if (nj < K) { dp2[nj] = min(dp2[nj], dp2[j] + C[i]); } else { int idx = 0; while (j + counter_sub[i][idx][1] < K) { ++idx; } int i_cnt = counter[i][2] - counter_sub[i][idx][2]; dp3[i_cnt] = min(dp3[i_cnt], dp2[j] + C[i]); } } } for (int i = 0; i < N; ++i) { for (int j = 0; j < K; ++j) { if (dp3[j] == LLONG_MAX) continue; int nj = j + counter[i][2]; if (nj < K) { dp3[nj] = min(dp3[nj], dp3[j] + C[i]); } else { dp3[K] = min(dp3[K], dp3[j] + C[i]); } } } if (dp3[K] == LLONG_MAX) { cout << -1 << endl; } else { cout << dp3[K] << endl; } return 0; }