AT_joi2018ho_c 団子職人 (Dango Maker)

你是一个包団子（日本传统食物，不要在意）的工匠。现在你要把団子串起来了。 所有的団子都放在一个正方形中，分为 $N$ 行和 $M$ 列。 每个点上有 $1$ 个団子。 每个団子的颜色为红色（R）、绿色（G）或白色（W）其中一种。你可以从左到右或从上到下连续取出 $3$ 个団子，然后按取出的顺序将 $3$ 个団子粘在 $1$ 个串上。 现在你想串尽可能多的串，但这些串上的団子必须按照 $1$ 个红、$1$ 个绿、$1$ 个白的顺序。另外，一个団子只能放在一个串上。

第一行为 $N$ 和 $M$，意义如上所述。 第二行到第 $N+1$ 行，每行 $M$ 个字符，代表団子的排列。

输出一个整数，代表你能串的最多的串数。

### 課題 マスの中に配置された団子の色の情報が与えられたとき，赤，緑，白の団子が $ 1 $ 個ずつこの順に刺さった串が最大何本作れるかを求めるプログラムを作成せよ． - - - - - - ### 制限 すべての入力データは以下の条件を満たす． - $ 1\ \leqq\ N\ \leqq\ 3\,000 $． - $ 1\ \leqq\ M\ \leqq\ 3\,000 $． ### 小課題 #### 小課題 1 \[13 点\] 以下の条件を満たす． - $ N\ \leqq\ 4 $． - $ M\ \leqq\ 4 $． #### 小課題 2 \[20 点\] 以下の条件を満たす． - $ N\ \leqq\ 10 $． - $ M\ \leqq\ 10 $． #### 小課題 3 \[67 点\] 追加の制限はない． - - - - - - ### Sample Explanation 1 次のように串に刺すことで，団子が刺さった串を $ 3 $ 本作ることができる． - 上から $ 1 $ 行目，左から $ 1 $ 列目の団子から右方向に $ 3 $ 個の団子を取り出し，この順に串に刺す． - 上から $ 1 $ 行目，左から $ 4 $ 列目の団子から下方向に $ 3 $ 個の団子を取り出し，この順に串に刺す． - 上から $ 3 $ 行目，左から $ 1 $ 列目の団子から右方向に $ 3 $ 個の団子を取り出し，この順に串に刺す． $ 4 $ 本以上の串を作ることはできないので，$ 3 $ を出力する． - - - - - - ### Sample Explanation 2 次のように串に刺すことで，団子が刺さった串を $ 4 $ 本作ることができる． - 上から $ 1 $ 行目，左から $ 1 $ 列目の団子から右方向に $ 3 $ 個の団子を取り出し，この順に串に刺す． - 上から $ 1 $ 行目，左から $ 4 $ 列目の団子から下方向に $ 3 $ 個の団子を取り出し，この順に串に刺す． - 上から $ 2 $ 行目，左から $ 2 $ 列目の団子から下方向に $ 3 $ 個の団子を取り出し，この順に串に刺す． - 上から $ 2 $ 行目，左から $ 3 $ 列目の団子から下方向に $ 3 $ 個の団子を取り出し，この順に串に刺す． $ 5 $ 本以上の串を作ることはできないので，$ 4 $ を出力する． - - - - - -