문제 설명

고대 피라미드의 각 층에는 보물이 있습니다. 꼭대기에서 시작해 바닥까지 내려가며 보물을 수집합니다. 각 위치에서 바로 아래 또는 오른쪽 아래로만 이동할 수 있을 때, 수집할 수 있는 보물의 최대 합을 구하세요.

입력

출력

제약 조건

• •1 <= 행 수 <= 500
• •-10000 <= 각 값 <= 10000

예제

[[7], [3, 8], [8, 1, 0], [2, 7, 4, 4]]

22