Apples and Bananas

Time limit1sMemory limit256 MB

Summary
Find a monotone down/right/diagonal path in an RxC grid to maximize apples below plus bananas above it, with R,C up to 1500.
Level

Medium6 of 10

Topics
Dynamic programming, Matrix, Implementation
Solved
No attempts yet

Problem

Country A and country B have argued over a border for years. The disputed land is a rectangle divided into R x C cells. Each cell contains either apple trees or banana trees.

A neutral negotiator, Sanggeun Kim, will use a bulldozer to remove all trees from some cells and use those cells as the border. The bulldozer starts at the upper-left cell and moves until it reaches the lower-right cell. Each move goes one cell down, one cell right, or one cell diagonally down-right.

Country A receives the land below the bulldozer's path, and country B receives the land above the path. It is possible for one country to receive no land.

People in country A like apples, and people in country B like bananas. Sanggeun therefore wants to maximize the sum of the number of apple trees below the path and the number of banana trees above the path.

Write a program that computes the maximum possible sum.

Input

The first line contains the size of the land, R and C. (2 <= R, C <= 1500)

Each of the next R lines describes one row. Every cell is written as a tree type followed by the number of trees in that cell. Apple trees are marked with A, and banana trees are marked with B. The number in each cell is between 1 and 99, inclusive.

Output

Print the maximum possible sum.

Hint

In the first public test case, the bulldozer can move diagonally down-right twice and then move down. The apple trees below the path total 3 + 2 + 4 = 9, and the banana trees above the path total 3 + 5 = 8, for a sum of 17.

Examples2

  1. Example 1

    Input
    4 3
B2 B3 B5
A3 B1 A1
A2 A4 B1
B1 B3 A3
    Expected output
    17

  2. Example 2

    Input
    3 5
A5 A2 B3 A6 B2
A1 B20 A5 B3 B6
A3 A5 B3 B8 A3
    Expected output
    37