소 파이 속 보물

소들이 금화가 든 파이를 잔뜩 구웠습니다! 각 파이에는 $N_i$개의 금화가 들어 있고($1 \le N_i \le 25$), 그 개수가 파이 껍질 위에 깔끔하게 적혀 있습니다.

소들은 목초지에 파이를 $R$행 $C$열의 격자로 가지런히 놓았습니다($1 \le R \le C \le 100$). 당신은 왼쪽 위, 즉 (행 $1$, 열 $1$) 위치에서 출발하여 그 칸의 금화를 즉시 얻습니다. 목초지 반대편으로 이동해야 하며, 한 번 움직일 때마다 반드시 열을 오른쪽으로 정확히 하나 옮겨야 하고, 마지막에는 (행 $R$, 열 $C$)에 도착해야 합니다.

다음 열로 옮길 때 행은 그대로 두거나 최대 $1$만큼만 바꿀 수 있습니다. 즉 $(r, c)$에서 $(r-1, c+1)$, $(r, c+1)$, $(r+1, c+1)$ 중 하나로 이동합니다. 격자 밖으로 나가서는 안 되며, 경로는 반드시 (행 $R$, 열 $C$)에서 끝나야 합니다. 지나는 칸의 금화는 모두 합계에 더해집니다.

목초지가 주어졌을 때, 모을 수 있는 금화의 최대 개수는 얼마일까요?

예를 들어 다음과 같은 목초지를 생각해 봅시다.

6 5 3 7 9 2 7
2 4 3 5 6 8 6
4 9 9 9 1 5 8

아래 경로는 $6 + 4 + 9 + 9 + 6 + 5 + 8 = 47$개의 금화를 모읍니다.

출발-> 6 5 3 7 9 2 7
        \
       2 4 3 5 6 8 6
          \   / \
       4 9 9-9 1 5-8 <-도착

다음 경로는 더 좋아서 $6 + 4 + 9 + 9 + 6 + 8 + 8 = 50$개를 모으며, 이것이 가능한 최댓값입니다.

출발-> 6 5 3 7 9 2 7
        \
       2 4 3 5 6-8 6
          \   /   \
       4 9 9-9 1 5 8 <-도착

• 첫째 줄: 공백으로 구분된 두 정수 $R$와 $C$
• 둘째 줄부터 $R+1$째 줄까지: 각 줄에 해당 행의 금화 개수 $C$개가 공백으로 구분되어 순서대로 주어집니다

• 첫째 줄: 모을 수 있는 금화의 최대 개수를 나타내는 정수 하나