module main; // https://kmjp.hatenablog.jp/entry/2015/10/16/0900 より // 動的計画法、文字列処理 import std; // aとbを比較してbの方が大きいならばaの値をbに更新する void chMax(T)(ref T a, in T b) { if (a < b) a = b; } // 多次元配列をある値で埋める void fill(A, T)(ref A a, T value) if (isArray!A) { alias E = ElementType!A; static if (isArray!E) { foreach (ref e; a) fill(e, value); } else { a[] = value; } } void main() { // 入力 auto S = readln.chomp; // 答えの計算 int L = S.length.to!int; auto dp = new int[][][][][](2, 21, 21, 21, 21); fill(dp, -1); dp[0][0][0][0][0] = 0; int ans = 0; foreach (i; 0 .. L) { int cur = i % 2, tar = cur ^ 1; dp[tar] = dp[cur].dup; foreach (a; 0 .. 21) foreach (b; 0 .. 21) foreach (c; 0 .. 21) foreach (d; 0 .. 21) { if (dp[cur][d][c][b][a] < 0) continue; int v = dp[cur][d][c][b][a]; if ((S[i] == 'K' || S[i] == '?') && a < 20) chMax(dp[tar][d][c][b][a + 1], v); if ((S[i] == 'U' || S[i] == '?') && b < 20 && a) chMax(dp[tar][d][c][b + 1][a - 1], v); if ((S[i] == 'R' || S[i] == '?') && c < 20 && b) chMax(dp[tar][d][c + 1][b - 1][a], v); if ((S[i] == 'O' || S[i] == '?') && d < 20 && c) chMax(dp[tar][d + 1][c - 1][b][a], v); if ((S[i] == 'I' || S[i] == '?') && d) chMax(ans, v + 1), chMax(dp[tar][d - 1][c][b][a], v + 1); } } // 答えの出力 writeln(ans); }