Ski jumping
Ski jumpers are individuals with a unique mindset. To achieve 200-meter flights, they require an iron will and a clear psychological state. Each jumper has their own way of preparing before a jump. Some listen to their favorite music, others mentally visualize the upcoming flight repeatedly. And some play the popular game «Bubble Breaker».
The game board consists of cells, each containing a ball of one of four colors: blue, red, green, or yellow. In each move, the player must remove any group of two or more adjacent balls of the same color. Cells are considered adjacent if they share a side. For each move, the player earns a score calculated as P*(P-1), where P is the number of balls in the removed group. The scores accumulate over the course of the game.
After removal, the balls above the cleared area fall vertically to fill the gaps. Naturally, a ball falls until it lands on an occupied cell. The game concludes when no more removable groups are available.
One jumper devised a strategy to enhance the greedy approach for this game. For each move, the following considerations are made:
If a move leads to a favorable situation for the subsequent move, execute this and the next move. Such a move is termed a first-type move.
If no such move exists, execute the optimal move. This is called a second-type move.
A move at step k leads to a favorable situation for the move at step k+1 if the move at step k+1 can yield more points than any other move at step k. A move at step k is considered optimal if it results in more points than any other move at step k.
If multiple suitable second-type moves exist, the area to be removed is the one located furthest to the left on the game board. If there are still several optimal moves, the area located highest on the game board should be removed. The position of the area is determined by the topmost cell from the leftmost cells of this area.
If there are several first-type moves, choose the move that will yield the maximum number of points on the next move. If there are still multiple such moves, select the optimal one among them (in case of possible equality of optimal moves, follow the aforementioned rule about choosing the area based on its position on the game board).
The athletes do not wish to be distracted from the competition for long, so they need you to determine the number of points that can be scored using this strategy.
Input
The first line contains the numbers N and M (1 ≤ N, M ≤ 50) – the dimensions of the game board. The game board follows with N rows of M characters from the set { Y, B, R, G }. Each character indicates the color of the ball: Y (yellow), B (blue), R (red), G (green).
Output
Output a single number – the total number of points.