0588 - イラン (IRAN)

問題

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

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

• 整数 i, j, k, l (i < j < k < l) を選んだ時の幸福度は, S_i = 'I', S_j = 'R', S_k = 'A', S_l = '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