Apples and Bananas

Two neighbouring villages, A and B, cannot settle a land dispute. The disputed area is a rectangle of $R \times C$ cells, and every cell holds either some apple trees or some banana trees.

An outside advisor was asked to mediate. He decided to send one bulldozer across the area and cut down every tree in the cells it passes. The bulldozer starts at the top left cell and always moves in one of three directions: right, down, or diagonally down and to the right. It stops when it reaches the bottom right cell.

Village A takes the land below the track and village B takes the land above it. In each row, the cells to the left of the cells the bulldozer passed are below the track, and the cells to the right of them are above the track. A village can end up with no cell at all.

The people of village A like apples and the people of village B like bananas. The advisor therefore picks the track that maximizes the number of apple trees left below it plus the number of banana trees left above it. Write a program that computes this maximum total.

The first line contains two integers $R$ and $C$ ($2 \le R, C \le 1500$), the size of the area.

Each of the next $R$ lines contains the descriptions of $C$ cells, separated by spaces. A description is the letter A (apples) or B (bananas) followed by the number of trees in that cell. Every cell holds between $1$ and $99$ trees.

Print the maximum total described above.

In the first example the bulldozer moves diagonally down and to the right, again diagonally down and to the right, then down. That leaves $3 + 2 + 4 = 9$ apple trees below the track and $3 + 5 = 8$ banana trees above it.