Happy birthday, Mii!

2 secs 1024 MB
Raclamusi

問題文


今日はみいちゃんの誕生日です。
Raclamusi君は誕生日プレゼントに文字列の mii! をたくさん用意しましたが、うっかり落としてバラバラになってしまいました。さらに悪いことに、いくつかの文字はなくなってしまったようです。Raclamusi君はいそいでバラバラになった文字列から mii! を取り出さなくてはなりません。

バラバラになった文字列を として、Raclamusi君は次の操作を繰り返して行います。

  • の連続する部分文字列に mii! が存在するならば、 から mii! つ取り除く。そうでなければ、 m , i , ! のいずれかを の好きな位置に挿入する。

を空にするのに必要な最小の操作回数を答えてください。

制約


  • に含まれる文字は m , i , ! のいずれかである。

入力


入力は以下の形式で与えられる。

出力


を空にするのに必要な最小の操作回数を出力せよ。

入出力例


入力例1
mimii!i!ii
出力例1
5

以下の 回の操作で を空にすることができます。

  • mi[mii!]i!ii
    番目から 番目までの文字を取り除く。
  • [mii!]ii
    番目から 番目までの文字を取り除く。
  • [m]ii
    番目に m を挿入する。
  • mii[!]
    番目に ! を挿入する。
  • [mii!]
    番目から 番目までの文字を取り除く。

入力例2
mii!mii!mii!mii!mii!
出力例2
5

入力例3
mmmmmmmmmm
出力例3
40

Submit


Go (1.14)