団子職人(Dango Maker)

あなたは団子を作る職人である．今，あなたは団子に串を刺そうとしているところである．

団子は，縦N 行，横M 列に仕切られたマスの中に配置されている．各マスには団子が1 個ずつ入っている．それぞれの団子には，赤(R)，緑(G)， 白(W) のいずれかの色が付いている．あなたは，左から右の方向，または，上から下の方向に連続する3 マスから団子を取り出し，この順に1 本の串にちょうど3個刺すことができる．

今あなたは，赤，緑，白の団子が1 個ずつこの順に刺さった串を可能な限り多く作りたい．串に刺す順番は，マスから取り出した順番と同じでなければならない．また，同じ団子に2 本以上の串を刺すことはできない．

あなたは，団子が刺さった串を最大何本作ることができるだろうか．

課題

マスの中に配置された団子の色の情報が与えられたとき，赤，緑，白の団子が1 個ずつこの順に刺さった串が最大何本作れるかを求めるプログラムを作成せよ．

入力

標準入力から以下の入力を読み込め．

• 1 行目には，整数N とM が空白を区切りとして書かれている．
• 続くN 行のうちのi 行目(1 \leq i \leq N) には，R, G, W からなる長さM の文字列が書かれている．この文字列のj 文字目(1 \leq j \leq M) は，上からi 行目，左からj 列目のマスの団子の色を表す．

出力

標準出力に，団子が刺さった串の本数の最大値を1 行で出力せよ．

制限

すべての入力データは以下の条件を満たす．

• 1 \leq N \leq 3 000．
• 1 \leq M \leq 3 000．

入出力例

入力例1

3 4
RGWR
GRGG
RGWW

出力例1

3

次のように串に刺すことで，団子が刺さった串を3 本作ることができる．

• 上から1 行目，左から1 列目の団子から右方向に3 個の団子を取り出し，この順に串に刺す．
• 上から1 行目，左から4 列目の団子から下方向に3 個の団子を取り出し，この順に串に刺す．
• 上から3 行目，左から1 列目の団子から右方向に3 個の団子を取り出し，この順に串に刺す．

4 本以上の串を作ることはできないので，3 を出力する．

入力例2

4 4
RGWR
GRRG
WGGW
WWWR

出力例2

4

次のように串に刺すことで，団子が刺さった串を4 本作ることができる．

• 上から1 行目，左から1 列目の団子から右方向に3 個の団子を取り出し，この順に串に刺す．
• 上から1 行目，左から4 列目の団子から下方向に3 個の団子を取り出し，この順に串に刺す．
• 上から2 行目，左から2 列目の団子から下方向に3 個の団子を取り出し，この順に串に刺す．
• 上から2 行目，左から3 列目の団子から下方向に3 個の団子を取り出し，この順に串に刺す．

5 本以上の串を作ることはできないので，4 を出力する．

入力例3

5 5
RGRGW
GRRGW
WGGWR
RWRGW
RGWGW

出力例3

6

情報オリンピック日本委員会作 『第17 回日本情報オリンピック(JOI 2017/2018) 本選』

---