Problem Description

You are a skilled dango maker. Currently, you are trying to skewer dangos on sticks.

The dangos are arranged in a grid of $N$ rows and $M$ columns. Each cell contains exactly one dango. Each dango is colored either red (R), green (G), or white (W). You can pick up dangos from three consecutive cells in either the left-to-right direction or the top-to-bottom direction and skewer exactly three dangos on one stick in this order.

You want to make as many sticks as possible with one red, one green, and one white dango in this order. The order of skewering must be the same as the order in which the dangos are picked up from the cells. Also, you cannot skewer more than one stick on the same dango.

How many sticks with dangos can you make at most?

Input Format

Read the following input from the standard input:

• The first line contains two integers $N$ and $M$ separated by a space.
• The next $N$ lines contain a string of length $M$ consisting of characters R, G, and W. The $j$-th character of the $i$-th line ($1 \leq i \leq N$, $1 \leq j \leq M$) represents the color of the dango in the cell at the $i$-th row and $j$-th column.

Output Format

Output the maximum number of sticks with dangos on them in one line to the standard output.

Sample Input and Output

Sample Input #1

3 4
RGWR
GRGG
RGWW

Sample Output #1

3

Sample Input #2

4 4
RGWR
GRRG
WGGW
WWWR

Sample Output #2

4

Sample Input #3

5 5
RGRGW
GRRGW
WGGWR
RWRGW
RGWGW

Sample Output #3

6

Notes/Hints

Task

Given the color information of dangos arranged in a grid, create a program that calculates the maximum number of sticks that can be made with one red, one green, and one white dango in this order.

Constraints

All input data satisfies the following conditions:

• $1 \leq N \leq 3,000$.
• $1 \leq M \leq 3,000$.

Subtasks

Subtask 1 [13 points]

Satisfies the following conditions:

• $N \leq 4$.
• $M \leq 4$.

Subtask 2 [20 points]

Satisfies the following conditions:

• $N \leq 10$.
• $M \leq 10$.

Subtask 3 [67 points]

No additional restrictions.

Sample Explanation 1

You can make 3 sticks with dangos by skewering as follows:
- Pick up 3 dangos from the first row, first column in the right direction and skewer them in this order.
- Pick up 3 dangos from the first row, fourth column in the down direction and skewer them in this order.
- Pick up 3 dangos from the third row, first column in the right direction and skewer them in this order.
Since you cannot make more than 3 sticks, output 3.

Sample Explanation 2

You can make 4 sticks with dangos by skewering as follows:
- Pick up 3 dangos from the first row, first column in the right direction and skewer them in this order.
- Pick up 3 dangos from the first row, fourth column in the down direction and skewer them in this order.
- Pick up 3 dangos from the second row, second column in the down direction and skewer them in this order.
- Pick up 3 dangos from the second row, third column in the down direction and skewer them in this order.
Since you cannot make more than 4 sticks, output 4.

见题面 Input 部分

见题面 Output 部分