// problem #74

정수 삼각형

삼각형 맨 위에서 아래로 내려가며 인접한 아래 칸을 선택할 때, 지나온 수의 합이 최대가 되는 값을 구하시오.

입력

첫 줄 삼각형 크기 N. 이후 N개 줄에 삼각형의 수.

출력

합의 최댓값.

제한

• 1 ≤ N ≤ 500
• 0 ≤ 각 수 ≤ 9,999

예제

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

30

1
9

9