#include #include using namespace std; using namespace atcoder; typedef long long ll; typedef long double ld; #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; i >= n; --i) #define ALL(v) (v).begin(),(v).end() #define ALLR(v) (v).rbegin(),(v).rend() #define fi first #define se second #define PB push_back #define EB emplace_back template using PQ = priority_queue; template using QP = priority_queue,greater>; templatevoid debug(const T &v,ll h,ll w){for(ll i=0;ivoid debug(const T &v,ll n){for(ll i=0;ivoid debug(const vector&v){debug(v,v.size());} templatevoid debug(const vector>&v){for(auto &vv:v)debug(vv,vv.size());} templatevoid debug(stack st){while(!st.empty()){cerr<void debug(queue st){while(!st.empty()){cerr<void debug(deque st){while(!st.empty()){cerr<void debug(PQ st){while(!st.empty()){cerr<void debug(QP st){while(!st.empty()){cerr<void debug(const set&v){for(auto z:v)cerr<void debug(const multiset&v){for(auto z:v)cerr<void debug(const array &a){for(auto z:a)cerr<void debug(const map&v){for(auto z:v)cerr<<"["<void foo(Head&& head, Tail&&... tail){cerr << head << " ";foo(move(tail)...);} templatebool chmax(T &a, const T &b) { if (abool chmin(T &a, const T &b) { if (b> s; int n=s.size(); vector dp(22,vector(22,vector(22,vector(22,vector(22))))); string t="KUROI"; dp[0][0][0][0][0]=true; REP(i,n){ vector tp(22,vector(22,vector(22,vector(22,vector(22))))); REP(a,21) REP(b,21)REP(c,21) REP(d,21) REP(e,21){ if(a+b+c+d+e>n) break; if(!dp[a][b][c][d][e]) continue; tp[a][b][c][d][e]=true; if(s[i]=='K'||s[i]=='?') tp[a+1][b][c][d][e]=true; if((s[i]=='U'||s[i]=='?')&&a) tp[a-1][b+1][c][d][e]=true; if((s[i]=='R'||s[i]=='?')&&b) tp[a][b-1][c+1][d][e]=true; if((s[i]=='O'||s[i]=='?')&&c) tp[a][b][c-1][d+1][e]=true; if((s[i]=='I'||s[i]=='?')&&d) tp[a][b][c][d-1][e+1]=true; } swap(dp,tp); } int ans=0; REP(a,21) REP(b,21)REP(c,21) REP(d,21) REP(e,21){ if(dp[a][b][c][d][e]) chmax(ans,e); } cout << ans << endl; }