今日はみいちゃんの誕生日です。
Raclamusi君は誕生日プレゼントに文字列の mii!
をたくさん用意しましたが、うっかり落としてバラバラになってしまいました。さらに悪いことに、いくつかの文字はなくなってしまったようです。Raclamusi君はいそいでバラバラになった文字列から mii!
を取り出さなくてはなりません。
バラバラになった文字列を として、Raclamusi君は次の操作を繰り返して行います。
mii!
が存在するならば、 から mii!
を つ取り除く。そうでなければ、 m
, i
, !
のいずれかを の好きな位置に挿入する。を空にするのに必要な最小の操作回数を答えてください。
m
, i
, !
のいずれかである。入力は以下の形式で与えられる。
を空にするのに必要な最小の操作回数を出力せよ。
mimii!i!ii
5
以下の 回の操作で を空にすることができます。
mi[mii!]i!ii
[mii!]ii
[m]ii
m
を挿入する。mii[!]
!
を挿入する。[mii!]
mii!mii!mii!mii!mii!
5
mmmmmmmmmm
40