PKU 3176. Cow Bowling

볼링치는 소

Time Limit: 1000MS	Memory Limit: 65536K
Total Submissions: 7685	Accepted: 5014

설명

소들은 진짜 볼링공을 굴려서 볼링을 치진 않습니다. 대신 각자 번호를 맡아서(번호의 범위는 0부터 99까지입니다) 자리를 잡고 볼링핀처럼 삼각형 모양으로 서있지요: 

          7



        3   8



      8   1   0



    2   7   4   4



  4   5   2   6   5

그러면 다른 소들이 삼각형의 맨 윗부분에서 시작해서, 아래쪽에 있는 가까운 두 마리 소 중 한 마리에게 움직입니다. 이러한 움직임을 가장 아래쪽에 내려갈 때까지 계속해서, 각 소의 점수는 지나온 경로의 소들의 번호들을 합한 값이 됩니다. (당연하지만) 합한 값이 제일 큰 소가 그 프레임의 우승자가 됩니다.

삼각형 대형의 줄 수는 N 개(1 <= N <= 350) 일 때, 가능한 경로중에서 숫자의 합이 가장 큰 값을 찾는것이 목표입니다.

입력

첫번째 줄: 하나의 정수 N 

두번째 줄부터 N+1 번째 줄 : i+1 번째 줄은  i 개의, 각 숫자 사이엔 공백으로 떨어져있는 정수들을 포함하는데,  삼각형 대형의 i 번째 줄을 나타냅니다.

출력

하나의 줄: 정해진 규칙을 따라 나올 수 있는 합의 최대값

입력 예시

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

출력 예시

30

Hint

Explanation of the sample: 

          7

         *

        3   8

       *

      8   1   0

       *

    2   7   4   4

       *

  4   5   2   6   5

The highest score is achievable by traversing the cows as shown above.

Source

USACO 2005 December Bronze