Maximum AK IOI Dango Strings

You are given an R×C grid. Each cell contains one dango with a color. You can form a string by choosing three consecutive dangos in a straight line (horizontal, vertical, or diagonal). The cells must be taken in order along that line (for example, top→middle→bottom or bottom→middle→top are allowed, but not top→bottom→middle).

A string is called an AK IOI string if the colors of the three dangos (in the order chosen) are either \( (G, W, P)\) or \( (P, W, G) \), where G stands for green, W for white, and P for pink.

Your task is to select a set of strings (each string covering three distinct cells) such that no cell is used in more than one string and the total number of AK IOI strings is maximized.

Note: The selection is done by tiling the grid with valid triomino placements. Each placement must cover three consecutive cells in one of the four directions below:

• Horizontal (left-to-right)
• Vertical (top-to-bottom)
• Diagonal down-right
• Diagonal down-left

The order matters: for a chosen placement, if the colors in the natural order are either \( (G, W, P) \) or \( (P, W, G) \), then the placement is valid.

Compute the maximum number of disjoint AK IOI strings that can be formed.

inputFormat

The first line contains two integers \(R\) and \(C\) (the number of rows and columns respectively).

Each of the next \(R\) lines contains \(C\) characters separated by spaces. Each character is one of G, W, or P, representing the color of the dango in that cell.

outputFormat

Output a single integer — the maximum number of disjoint AK IOI strings that can be formed.

sample

3 3
G W P
P W G
G W P

3