사과와 바나나

A나라와 B나라가 국경선을 두고 오랫동안 다투고 있다. 분쟁 지역은 직사각형이며, R x C개의 칸으로 나뉘어 있다. 각 칸에는 사과나무 또는 바나나나무가 심어져 있다.

중립국의 협상가 김상근은 불도저로 일부 칸의 나무를 모두 제거하고, 그 칸들을 국경선으로 삼으려 한다. 불도저는 가장 왼쪽 위 칸에서 출발해 가장 오른쪽 아래 칸에 도착할 때까지 이동한다. 한 번에 아래, 오른쪽, 오른쪽 아래 대각선 방향으로 한 칸 이동할 수 있다.

A나라는 불도저가 지나간 경로의 아래쪽 땅을 가지고, B나라는 경로의 위쪽 땅을 가진다. 어느 한 나라가 땅을 전혀 받지 못할 수도 있다.

A나라 사람들은 사과를 좋아하고 B나라 사람들은 바나나를 좋아한다. 따라서 김상근은 경로 아래쪽에 있는 사과나무 수와 경로 위쪽에 있는 바나나나무 수의 합을 최대화하려고 한다.

가능한 합의 최댓값을 구하는 프로그램을 작성하시오.

첫째 줄에 땅의 크기 R과 C가 주어진다. (2 <= R, C <= 1500)

다음 R개 줄에는 각 칸에 심어진 나무의 종류와 그 수가 주어진다. 사과는 A, 바나나는 B로 표시되며, 뒤에는 그 칸의 나무 수가 붙는다. 각 칸의 나무 수는 1 이상 99 이하이다.

가능한 합 중 최댓값을 출력한다.

첫 번째 공개 테스트 케이스에서는 불도저가 오른쪽 아래 대각선으로 두 번 이동한 뒤 아래로 이동하면 된다. 이때 경로 아래쪽의 사과나무 수는 3 + 2 + 4 = 9이고, 경로 위쪽의 바나나나무 수는 3 + 5 = 8이므로 합은 17이다.