Dango Maker

Time limit2sMemory limit256 MB

Summary

Choose disjoint horizontal or vertical runs of three cells reading R, G, W in order on an N by M grid, maximizing how many such sticks fit.

Level: Hard8 of 10
Topics: Dynamic programming, Matrix, Implementation, Greedy
Solved: No attempts yet

Problem

You are a professional confectioner who makes dango, Japanese sweet dumplings. You are about to put the dumplings on skewers.

The dumplings sit on a grid of cells with $N$ rows and $M$ columns, one dumpling per cell. Each dumpling is red (R), green (G), or white (W).

To make one stick, you choose three consecutive cells and skewer their dumplings. The three cells must run from left to right or from top to bottom.

You want sticks whose dumplings are red, green, and white, in this order, and you want to make as many such sticks as possible. The order of the dumplings on a stick is the order in which they were chosen from the grid. A dumpling cannot be on more than one stick.

Given the colors of the dumplings on the grid, write a program that computes the maximum number of sticks you can make. The colors on every stick must be red, green, white, in this order.

Input

Read the following data from standard input.

The first line contains two integers $N$ and $M$ separated by a space.
The $i$ -th of the next $N$ lines ( $1 \le i \le N$ ) contains a string of length $M$ consisting of the characters R, G, and W. The $j$ -th character ( $1 \le j \le 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.

Output

Write one line to standard output containing the maximum number of sticks you can make.

Constraints

$1 \le N \le 3000$
$1 \le M \le 3000$

Examples3

Example 1
Input
```
3 4
RGWR
GRGG
RGWW
```
Expected output
```
3
```
Example 2
Input
```
4 4
RGWR
GRRG
WGGW
WWWR
```
Expected output
```
4
```
Example 3
Input
```
5 5
RGRGW
GRRGW
WGGWR
RWRGW
RGWGW
```
Expected output
```
6
```