문제
꿀꿀이 올림피아드에 새로운 종목인 볼링이 추가되었다. 하지만 일반적인 볼링을 할 수 없는 꿀꿀이들은 나름대로의 규칙을 만들었다.
아래 그림과 같이 삼각형 모양의 볼링핀을 세운다. 볼링핀에는 0에서 99까지의 정수가 적혀있다. 맨 위에 행에서 맨 아래 행으로 진행하는데 좌 우 대각선 열로 이동한다. 맨 아래 행까지 오면 그때까지 만난 볼링핀에 적힌 점수의 합으로 스코어를 계산한다.
볼링핀에 대한 정보가 주어질 때 최대 점수는 얼마나 될까?
입력
첫 행에 행의 수 N(1 ≤ N ≤ 350)이 주어진다. 이어서 N개의 행에 걸쳐 볼링핀의 점수를 나타내는 정수가 공백으로 구분되어 주어진다.
출력
획득할 수 있는 최대 점수를 출력하시오.
예제1
입력
5
7
38
810
2744
45265
출력
30
출처
USACO 2005 December Bronze