#include using namespace std; typedef long long ll; #define REP(i,n) for(int i=0,_n=(int)(n);i<_n;++i) #define ALL(v) (v).begin(),(v).end() #define CLR(t,v) memset(t,(v),sizeof(t)) templateostream& operator<<(ostream& os,const pair&a){return os<<"("<void pv(T a,T b){for(T i=a;i!=b;++i)cout<<(*i)<<" ";cout<void chmin(T&a,const T&b){if(a>b)a=b;} templatevoid chmax(T&a,const T&b){if(a> s; int N = s.size(); map, int> dp; dp.insert( make_pair( vector(4), 0) ); // [0,0,0,0] REP(i, N) { if (string("KUROI?").find(s[i]) == string::npos) continue; map, int> ndp; for (auto it = dp.begin(); it != dp.end(); ++it) { const vector state = it->first; const int val = it->second; vector n_state = state; chmax(ndp[n_state], val); if (s[i] == 'K') { if (n_state[0] <= 20) n_state[0]++; chmax(ndp[n_state], val); } if (s[i] == 'U') { if (n_state[0] > 0) { n_state[0]--; if (n_state[1] <= 20) n_state[1]++; chmax(ndp[n_state], val); } } if (s[i] == 'R') { if (n_state[1] > 0) { n_state[1]--; if (n_state[2] <= 20) n_state[2]++; chmax(ndp[n_state], val); } } if (s[i] == 'O') { if (n_state[2] > 0) { n_state[2]--; if (n_state[3] <= 20) n_state[3]++; chmax(ndp[n_state], val); } } if (s[i] == 'I') { if (n_state[3] > 0) { n_state[3]--; chmax(ndp[n_state], val + 1); } } if (s[i] == '?') { for (char ch : string("KUROI")) { vector n_state = state; if (ch == 'K') { if (n_state[0] <= 20) n_state[0]++; chmax(ndp[n_state], val); } if (ch == 'U') { if (n_state[0] > 0) { n_state[0]--; if (n_state[1] <= 20) n_state[1]++; chmax(ndp[n_state], val); } } if (ch == 'R') { if (n_state[1] > 0) { n_state[1]--; if (n_state[2] <= 20) n_state[2]++; chmax(ndp[n_state], val); } } if (ch == 'O') { if (n_state[2] > 0) { n_state[2]--; if (n_state[3] <= 20) n_state[3]++; chmax(ndp[n_state], val); } } if (ch == 'I') { if (n_state[3] > 0) { n_state[3]--; chmax(ndp[n_state], val + 1); } } } } } dp.swap(ndp); } int ans = 0; for (auto it = dp.begin(); it != dp.end(); ++it) { chmax(ans, it->second); } cout << ans << endl; return 0; } int main() { #ifdef LOCAL for (;!cin.eof();cin>>ws) #endif main2(); return 0; }