第 16 回 日本情報オリンピック　模擬予選 ３

2016年12月10日
E869120, square1001

問題

JOI 君は, IOI 2017 イラン大会に行くことになったので, IRANという文字列が大好きである. JOI 君は, ある文字列の部分列に IRAN が含まれていればうれしく感じるが, それぞれの文字の間隔が遠い方がさらにうれしく感じる.

そこで, 文字列 S から得られる幸福度は, 次のように定義される. ここで, 文字列 S の i 番目の文字を Si と表記する.

• 整数 i, j, k, l (i < j < k < l) を選んだ時の幸福度は, Si = 'I', Sj = 'R', Sk = 'A', Sl = 'N' を満たしていれば (j-i)(k-j)(l-k) であり, そうでなければ 0 である.
• 文字列 S の幸福度は, 上手く整数 i, j, k, l を選んだ時に得られる幸福度の最大値である.

このとき, 文字列 S の幸福度を求めよ.

入力

入力は 1 行からなる.

1 行目に文字列 S が与えられる. S は 1 文字以上 800 文字以下の英大文字のみから成る文字列である.

出力

1 行に, 文字列 S の幸福度を出力せよ.

入出力例

IOIIRANTWENTYSEVENTEEN
  

LETSENJOYTHISCONTEST
  

64
   

0
   

※各入出力例のデータは，右クリック等によりファイルに保存して利用可能です．

採点用データ