10084 정수 삼각형 Silver I

문제

삼각형의 맨 위층부터 아래층까지 내려오면서, 대각선 왼쪽 또는 대각선 오른쪽으로 이동할 때, 거쳐간 수의 합이 최대가 되는 경우를 구하시오.

입력

첫째 줄에 삼각형의 크기 N (1 ≤ N ≤ 500)이 주어진다. 다음 N개의 줄에 삼각형이 주어진다. 각 수는 0 이상 9,999 이하이다.

출력

거쳐간 수의 합의 최댓값을 출력한다.

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

30