꿀꿀이 올림피아드에 새로운 종목인 볼링이 추가되었다. 하지만 일반적인 볼링을 할 수 없는 꿀꿀이들은 나름대로의 규칙을 만들었다.

아래 그림과 같이 삼각형 모양의 볼링핀을 세운다.

볼링핀에는 0에서 99까지의 정수가 적혀있다.

맨 위에 행에서 맨 아래 행으로 진행하는데 좌 우 대각선 열로 이동한다.

맨 아래 행까지 오면 그때까지 만난 볼링핀에 적힌 점수의 합으로 스코어를 계산한다.

볼링핀에 대한 정보가 주어질 때 최대 점수는 얼마나 될까?

첫 행에 행의 수 N(1 ≤ N ≤ 350)이 주어진다.
이어서 N개의 행에 걸쳐 볼링핀의 점수를 나타내는 정수가 공백으로 구분되어 주어진다.

획득할 수 있는 최대 점수를 출력하시오.