1375 - 소가 하는 볼링

Time Limit: 1s Memory Limit: 128MB

Submissions: 140 Solved: 73
Description

소들은 볼링을 칠 때 실제 볼링 핀을 사용하지 않습니다. 그들은 대신 0~99까지의 숫자를 하나 가지고 볼링 핀 배열과 같은 삼각형의 형태를 취합니다. 예를 들면.. 아래처럼 말이죠

          7


3 8

8 1 0

2 7 4 4

4 5 2 6 5

볼링 공 역할을 수행하는 소는 삼각형의 꼭대기에서 부터 아래 방향으로 좌측 혹은 우측 소를 선택하면서 가장 아래까지 이동합니다. 볼링 공 소의 점수는 이동하면서 거친 볼링 핀 소가 가지고 있는 점수의 합입니다. 가장 높은 점수를 가진 소가 우승하게 됩니다.

N(1~350) 줄의 삼각형이 주어졌을 때, 획득 가능한 가장 큰 점수는 몇점일까요?

Input

* Line 1 : 단일 정수 N (삼각형이 가지는 줄-row-의 수)

* Line 2 ~ N+1 : (라인 번호 - 1)개의 정수

Output

* Line 1 : 이동 과정에서 얻을 수 있는 최고 점수

Sample Input
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
Sample Output
30
Hint

샘플에 대해 가장 높은 점수를 획득할 수 있는 이동 경로는 아래와 같습니다. *가 각 과정에서 선택한 이동 경로입니다.

          7


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