사과와 바나나

이웃한 두 마을 A와 B가 땅을 두고 다투고 있다. 분쟁 지역은 $R \times C$개의 칸으로 이루어진 직사각형이고, 각 칸에는 사과나무 몇 그루 또는 바나나나무 몇 그루가 심겨 있다.

중재를 맡은 고문은 이 지역에 불도저를 한 대 통과시켜 불도저가 지나간 칸의 나무를 모두 베어내기로 했다. 불도저는 왼쪽 위 칸에서 출발해 오른쪽, 아래쪽, 오른쪽 아래 대각선 중 한 방향으로만 움직이고, 오른쪽 아래 칸에 도착하면 멈춘다.

불도저가 낸 길을 기준으로 길 아래쪽 땅은 A 마을이, 길 위쪽 땅은 B 마을이 가진다. 각 행에서 불도저가 지나간 칸보다 왼쪽에 있는 칸이 길 아래쪽이고, 오른쪽에 있는 칸이 길 위쪽이다. 한 마을이 칸을 하나도 받지 못할 수도 있다.

A 마을 사람은 사과를 좋아하고 B 마을 사람은 바나나를 좋아한다. 고문은 길 아래쪽에 남은 사과나무 수와 길 위쪽에 남은 바나나나무 수의 합이 최대가 되도록 길을 정하려고 한다. 이 합의 최댓값을 구하는 프로그램을 작성하시오.

첫째 줄에 지역의 크기를 나타내는 정수 $R$과 $C$가 주어진다. ($2 \le R, C \le 1500$)

다음 $R$개 줄에는 각각 칸 $C$개의 정보가 공백으로 구분되어 주어진다. 한 칸의 정보는 사과를 뜻하는 문자 A 또는 바나나를 뜻하는 문자 B 뒤에 그 칸에 심긴 나무 수를 붙여 쓴 것이다. 한 칸의 나무 수는 $1$ 이상 $99$ 이하이다.

위에서 설명한 나무 수의 합의 최댓값을 출력한다.

첫 번째 예제에서 불도저가 오른쪽 아래 대각선, 오른쪽 아래 대각선, 아래 순서로 움직이면 길 아래쪽에 사과나무가 $3 + 2 + 4 = 9$그루, 길 위쪽에 바나나나무가 $3 + 5 = 8$그루 남는다.