Typical DP Contest

I - イウィ


Time limit時間制限 : 2sec / Memory limitメモリ制限 : 262.144MB

Problem Statement

s は i と w からなる文字列である。すぬけ君は、この中から連続する三文字が "iwi" となっている部分を取り除く操作を繰り返すことができる。(iwi を取り除くと、その左側と右側にあった文字列が連結され、長さが三文字短い新しい文字列ができる。) 操作を行うことのできる回数の最大値を求めよ。

Constraints

  • 1 ≤ |s| ≤ 300
  • Each character in s will be either 'i' or 'w'.

Input Format

入力は以下の形式で標準入力から与えられる。
s

Output Format

答えを一行に出力せよ。

Sample Input 1

iwiwii

Sample Output 1

2
先に 3 文字目から 5 文字目の iwi を取り除くのが最適である。

Sample Input 2

iwiwwwiiiwiwiwiiwii

Sample Output 2

5

Submit提出する