Informatica Online Judge

  젖소 볼링 (NTTP) [0209 / 00D1]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 276   Total Tried : 350


The Champion of this Problem (C++) : gs16103 - 0ms / 161byte
My Best Submission (C++) : N/A

[]

Background

USACO나라의 소들은 볼링을 즐길 줄 안다. 하지만 그 소들은 일반적인 방법이 아닌 독특한 방법으로 볼링점수를 계산한다. 볼링 핀을 삼각형태로 배치한 다음 맨 위의 핀에서 아래로 내려가는데 대각선으로 연결된 핀으로만 내려가면서 점수를 합산해 나간다. 그래서 맨 아래 부분에 도착했을 때 점수의 합이 최고인 소가 이기는 것이 바로 소 볼링게임의 규칙이다. 현재 주어진 핀을 입력으로 받아서 소들이 얻을 수 있는 가장 최고 점수를 알아내는 프로그램을 작성하시오.



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

Input

첫 번째 줄에 볼링핀의 높이 N이 입력된다. (1 <= N <= 350) 둘 째줄부터 N+1번째 줄까지 각 볼링핀과 그 점수가 차례로 주어진다.

Output

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

IO Example

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

출력
30


출처 : USACO (http://ace.delos.com)

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]