USACO나라의 소들은 볼링을 즐길 줄 안다. 하지만 그 소들은 일반적인 방법이 아닌 독특한 방법으로 볼링점수를 계산한다.

볼링 핀을 삼각형태로 배치한 다음 맨 위의 핀에서 아래로 내려가는데 대각선으로 연결된 핀으로만 내려가면서 점수를 합산해 나간다.

그래서 맨 아래 부분에 도착했을 때 점수의 합이 최고인 소가 이기는 것이 바로 소 볼링게임의 규칙이다.

현재 주어진 핀을 입력으로 받아서 소들이 얻을 수 있는 가장 최고 점수를 알아내는 프로그램을 작성하시오.

          7

        3   8

      8   1   0

    2   7   4   4

  4   5   2   6   5

높이가 5이고 볼링핀이 다음과 같이 주어질 경우 최대 값은 30이 된다. (이 경우 경로는 7-3-8-7-5이다.)

첫 번째 줄에 볼링핀의 높이 N이 입력된다. (1 <= N <= 350)

둘 째줄부터 N+1번째 줄까지 각 볼링핀과 그 점수가 차례로 주어진다.

얻을 수 있는 최대 점수를 출력한다.