//#pragma GCC optimize("Ofast") //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") //#pragma GCC optimize("unroll-loops") //#pragma warning(disable : 4996) #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define REP(i, n) for(int i = 0;i < n;++i) #define REPR(i, n) for(int i = n-1;i >= 0;--i) #define FOR(i, m, n) for(int i = m;i < n;++i) #define FORR(i, m, n) for(int i = m-1;i >= n;--i) #define SORT(v, n) sort(v, v+n); #define VSORT(v) sort(v.begin(), v.end()); #define REVERSE(v,n) reverse(v,v+n); #define VREVERSE(v) reverse(v.begin(), v.end()) #define ll long long #define print(x) cout<<(x)<<'\n' #define pe(x) cout<<(x)<<" " #define DEBUG(x) cout<<#x<<": "< inline void chmin(T1 & a, T2 b) { if (a > b) a = b; } template inline void chmax(T1& a, T2 b) { if (a < b) a = b; } typedef pairpii; typedef array arr3; std::random_device rd; std::mt19937 mt(rd()); constexpr ll MOD = 1e9 + 7; constexpr int MAX = 2000020; const double pi = acos(-1); constexpr double EPS = 1e-8; constexpr ll INF = 1e18; void yes(bool c) { if (c)print("Yes"); else print("No"); }; //const int mod = 1000000007; const int mod = 998244353; struct mint { ll x; // typedef long long ll; mint(ll x = 0) :x((x%mod + mod) % mod) {} mint operator-() const { return mint(-x); } mint& operator+=(const mint a) { if ((x += a.x) >= mod) x -= mod; return *this; } mint& operator-=(const mint a) { if ((x += mod - a.x) >= mod) x -= mod; return *this; } mint& operator*=(const mint a) { (x *= a.x) %= mod; return *this; } mint operator+(const mint a) const { return mint(*this) += a; } mint operator-(const mint a) const { return mint(*this) -= a; } mint operator*(const mint a) const { return mint(*this) *= a; } mint pow(ll t) const { if (!t) return 1; mint a = pow(t >> 1); a *= a; if (t & 1) a *= *this; return a; } // for prime mod mint inv() const { return pow(mod - 2); } mint& operator/=(const mint a) { return *this *= a.inv(); } mint operator/(const mint a) const { return mint(*this) /= a; } }; istream& operator>>(istream& is, const mint& a) { return is >> a.x; } ostream& operator<<(ostream& os, const mint& a) { return os << a.x; } ll dp[301000]; string S[100]; ll C[101]; void solve() { int N, K; cin >> N >> K; string T; REP(i, K)T += 'J'; REP(i, K)T += 'O'; REP(i, K)T += 'I'; REP(i, 100)T += '.'; REP(i, N) { cin >> S[i] >> C[i]; } REP(i, 3 * K + 100)dp[i] = 1e18; dp[0] = 0; REP(i, 3 * K) { REP(j, N) { int stride = 0; int idx = i; REP(k, S[j].size()) { if (T[idx] == S[j][k]) { idx++; } } chmin(dp[idx], dp[i] + C[j]); } } if (dp[3 * K] == 1e18)print(-1); else print(dp[3 * K]); } signed main() { cin.tie(0); ios::sync_with_stdio(false); //int q; cin >> q; //while (q--) solve(); }