ダイナミックプログラミングダイナミックプログラミング:金鉱

#입력1
3 4
1 3 3 2 2 1 4 1 0 6 4 7
#출력1
19

#입력2
4 4
1 3 1 5 2 2 4 1 5 0 2 3 0 6 1 2
#출력2
16

n, m = map(int, input().split())
array = list(map(int, input().split(" ")))

n = 3
m = 4
array = [1,3,3,2
        ,2,1,4,1
        ,0,6,4,7]

dp = []
idx = 0

for i in range(n):
  dp.append(array[idx:idx+m])
  idx += m

for j in range(1, m): # 두번째 열부터 마지막열까지
    for i in range(n): # 첫번째 행부터 마지막 행까지
        # 왼쪽에서 오는 경우
        left = dp[i][j - 1]

        # 왼쪽 위에서 오는 경우
        if i == 0 : left_up = 0 # 위쪽 벽 넘으면 0
        else: left_up = dp[i-1][j-1]

        # 왼쪽 아래에서 오는 경우
        if i == n-1 : left_down = 0 # 아래쪽 벽 넘으면 0
        else: left_down = dp[i+1][j-1]

        dp[i][j] = dp[i][j] + max(left_up, left_down, left)

result = 0
for i in range(n):
    result = max(result, dp[i][m-1])
print(result)