from itertools import product def solve(): SS = input() S = [c for c in SS if c in 'KUROI?'] L1 = len(S) L2 = L1 // 5 + 1 dp = [[[[[-1 for o in range(L2)] for r in range(L2)] for u in range(L2)] for k in range(L2)] for x in range(L1 + 1)] # dp[x][k][u][r][o] = 次に見るのが x 文字目で、 kまで: k個、uまで: u個、rまで: r個、oまで: o個 のとき、i までできた数 dp[0][0][0][0][0] = 0 ma = 0 for x, c in enumerate(S): dpx = dp[x] for k, u, r, o in product(range(L2), repeat=4): if dpx[k][u][r][o] < 0: continue now = dpx[k][u][r][o] dpy = dp[x + 1] if (c == 'K' or c == '?') and k < 20: dpy[k + 1][u][r][o] = max(dpy[k + 1][u][r][o], now) if (c == 'U' or c == '?') and u < 20 and k: dpy[k - 1][u + 1][r][o] = max(dpy[k - 1][u + 1][r][o], now) if (c == 'R' or c == '?') and r < 20 and u: dpy[k][u - 1][r + 1][o] = max(dpy[k][u - 1][r + 1][o], now) if (c == 'O' or c == '?') and o < 20 and r: dpy[k][u][r - 1][o + 1] = max(dpy[k][u][r - 1][o + 1], now) if (c == 'I' or c == '?') and o: dpy[k][u][r][o - 1] = max(dpy[k][u][r][o - 1], now + 1) ma = max(ma, now + 1) print(ma) if __name__ == '__main__': solve()