配点: 100 点
你是一个包饺子的工匠。现在你要把饺子串起来了。
饺子是竖着的 N 行,横 M 它被放置在一个分为几列的正方形中。每个方格里都有一个饺子 包含 1 块。每个饺子的颜色分别为红色(R)、绿色(G)或白色(W)。您可以从左到右或从上到下继续。 3 从方格中取出饺子并按顺序放置。 1 就在书串上 3 你可以进行单独的刺击。
现在你有红、绿、白三种饺子了。 1 我想制作尽可能多的串,每个串都按这个顺序刺穿。棋子串起来的顺序必须与它们从方格中移除的顺序相同。另外,在同一个饺子里 2 不能插入比书还大的串。
你能包多少串饺子?
課題
当给出有关放置在正方形中的团子颜色的信息时,红色、绿色和白色团子 1 编写一个程序,找出按此顺序插入每块可以制作的最大串数。
入力
从标准输入读取以下输入。
- 1 行包含一个整数 N 和 M 以空格作为分隔符。 长度由
- 继续 N 行 i 行目 (1 \leqq i \leqq N)有
R,G,W组成 写入字符串 M 。这个字符串的 j 文字目 (1 \leqq j \leqq M) 来自上面 i 线,从左起 j 代表该列中方格内饺子的颜色。
出力
最大串饺子数输出到标准输出。 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 点]
没有其他限制。
入力例 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