BAGER

문제

Inhabitants of neighbouring villages (call the villages A and B) cannot settle their border dispute. The disputed area is rectangular, composed of R×C unit cells of land. Every cell has either some number of apple trees or some number of banana trees growing in it. 

A foreign counsellor has been asked to mediate in order to settle the dispute. He has decided that a bulldozer will pass through the area and destroy all trees in the cells it goes through. The bulldozer will start in the upper-left corner of the area and always move one cell down, right or diagonally down-right. 

The bulldozer stops when it reaches the lower-right corner. 

The village A will get the land below the bulldozer's path, while village B will get the land above it. Note that it is possible for one of the villages to receive no land at all. 

The counsellor noticed that people in village A prefer apples, while people in village B prefer bananas. So he decided to choose the bulldozer's path so that the sum of the numbers of apple trees below its path and banana trees above its path is the largest possible. 

Write a program that calculates this largest possible sum. 

입력

The first line contains the integers R and C (2 ≤ R, C ≤ 1500), the dimensions of the area. 

Each of the following R lines contains C descriptions of a cell of land. Each such description consists of the letter 'A' (apples) or 'B' (bananas) and the number of such trees in the cell. Each cell contains between 1 and 99 trees. 

출력

Output the largest possible sum as described above. 

 

힌트

In the first example, the bulldozer should move down-right, down-right and down. There will be 3+2+4=9 apple trees below its path and 3+5=8 banana trees above the path.

4 3
B2 B3 B5
A3 B1 A1
A2 A4 B1
B1 B3 A3

17

3 5
A5 A2 B3 A6 B2
A1 B20 A5 B3 B6
A3 A5 B3 B8 A3

37