Happy birthday, Mii!

2 secs 1024 MB
Raclamusi's icon Raclamusi

問題文

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

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

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

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

制約

  • 1S1001 \le |S| \le 100
  • SS に含まれる文字は m , i , ! のいずれかである。

入力

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

SS

出力

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

入出力例

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

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

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

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

入力例3
mmmmmmmmmm
出力例3
40

Submit


Go (1.21)