시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 256 MB3161038833.333%

문제

You are a professional confectioner making dangos, Japanese sweet dumplings. Now, you are about to skewer the dumplings.

The dumplings are placed on a grid of cells with N rows and M columns. Each cell contains one dumpling. The color of each dumpling is either red (R), green (G), or white (W).

You will choose three consecutive dumplings from the cells, and skewer them to a stick. The direction of the chosen three consecutive dumplings must be from left to right, or from top to bottom.

Now, you want to make sticks of dumplings whose colors are red, green, white, in this order. You want to make as many sticks of dumplings as possible. The order of dumplings skewered to a stick must be the same as the order of dumplings chosen from the cells. You are not allowed to skewer more than one sticks to one dumpling.

How many sticks of dumplings can you make?

Given the colors of dumplings placed on the cells, write a program which calculates the maximum number of sticks of dumplings you can make. The colors must be red, green, white, in this order.

입력

Read the following data from the standard input.

  • The first line of input contains two space separated integers N and M.
  • The i-th line (1 ≤ i ≤ N) of the following N lines contains a string of size M consisting of R, G, or W. The j-th character (1 ≤ j ≤ M) of this string is the color of the dumpling in the i-th row from the top, and the j-th column from the left.

출력

White one line to the standard output. The output should contain the maximum number of sticks of dumplings.

제한

  • 1 ≤ N ≤ 3 000.
  • 1 ≤ M ≤ 3 000.

서브태스크

번호배점제한
113

N ≤ 4, M ≤ 4.

220

N ≤ 10, M ≤ 10.

367

There are no additional constraints.

예제 입력 1

3 4
RGWR
GRGG
RGWW

예제 출력 1

3

By the following way, you can make 3 sticks of dumplings.

  • You choose three consecutive dumplings from the first row from top, and the first column from left. The direction is from left to right. Then, you skewer them to a stick in this order.
  • You choose three consecutive dumplings from the first row from top, and the 4-th column from left. The direction is from top to bottom. Then, you skewer them to a stick in this order.
  • You choose three consecutive dumplings from the third row from top, and the first column from left. The direction is from left to right. Then, you skewer them to a stick in this order.

Since you cannot make 4 sticks, output 3.

예제 입력 2

4 4
RGWR
GRRG
WGGW
WWWR

예제 출력 2

4

By the following way, you can make 4 sticks of dumplings.

  • You choose three consecutive dumplings from the first row from top, and the first column from left. The direction is from left to right. Then, you skewer them to a stick in this order.
  • You choose three consecutive dumplings from the first row from top, and the 4-th column from left. The direction is from top to bottom. Then, you skewer them to a stick in this order.
  • You choose three consecutive dumplings from the second row from top, and the second column from left. The direction is from top to bottom. Then, you skewer them to a stick in this order.
  • You choose three consecutive dumplings from the second row from top, and the third column from left. The direction is from top to bottom. Then, you skewer them to a stick in this order.

Since you cannot make 5 sticks, output 4.

예제 입력 3

5 5
RGRGW
GRRGW
WGGWR
RWRGW
RGWGW

예제 출력 3

6

채점 및 기타 정보

  • 예제는 채점하지 않는다.