# 11048 이동하기

n,m = map(int,input().split()) # n : 열 m : 행

candy = []
for i in range(n):
  candy.append(list(map(int,input().split())))

dp = [ [0]*m for i in range(n) ]

for i in range(n):
  for j in range(m):

    a = i -1
    b = j -1

    tmp = [0] 

    if a >= 0 : 
      tmp.append( dp[a][j] )
    if b >=0 :
      tmp.append( dp[i][b] )
    if a >= 0 and b >=0 : 
      tmp.append( dp[a][b] )
    
    dp[i][j] = candy[i][j] + max(tmp)

print(dp[n-1][m-1])

 

dp 에 각 칸에서 가질 수 있는 최대 사탕의 수를 입력한다. 

문제에서 움직일 수 있는 경로가 3개 밖에 없으므로 간단하게 구현할 수 있다. 

 

점화식 : 현재 칸에서의 사탕의 최대 수 :  ( 이동 전 칸이 될 수 있는 곳들 중 사탕의 최대 수 ) + 현재 칸의 사탕 수