프로그램 명: usa_pogocow
제한시간: 1 초

농부 존은 그의 소중한 암소 베씨의 기동력을 향상시키기 위해 베씨의 다리에 스카이 콩콩을 붙였다. 덕분에 베씨는 농장 주변을 빠르게 뛰어다닐 수 있게 되었으나, 아직 어떻게 속도를 줄이는지를 배우지 못했다.

베씨의 뛰어다니는 훈련을 돕기 위해, 농부 존은 농장에 일직선 경로를 설치하였다. 존은 N개의 목적지를 서로 다른 위치마다 설정하였다. (1<=N<=1,000)

목적지는 x(i)에 위치하고, 만약 베씨가 목적지에 도달하면 p(i)의 점수를 획득하게 된다. 베씨는 어느 목적지에서 출발해도 상관없고, 목적지들만을 밟아서 한 방향으로 이동해야된다. 뛰는 거리는 적어도 이전에 뛴 것만큼은 뛰어야되며 목적지로 꼭 가야 된다.

목적지의 위치와 점수들이 주어질 때, 베씨가 얻을 수 있는 최대 점수를 출력하시오.

입력

출력

베씨가 받을 수 있는 최대 점수를 출력하시오.

입출력 예 

입력 

6 
5 6 
1 1 
10 5 
7 6 
4 8 
8 10 

출력 

25

입출력 보충

베씨가 x=4 에서 출발해서 x=5, x=7, x=10 을 방문하면 점수는 (8,6,6,5)를 획득하게 되어 25점이 된다.
In an ill-conceived attempt to enhance the mobility of his prize cow Bessie, Farmer John has attached a pogo stick to each of Bessie's legs. Bessie can now hop around quickly throughout the farm, but she has not yet learned how to slow down.

To help train Bessie to hop with greater control, Farmer John sets up a practice course for her along a straight one-dimensional path across his farm. At various distinct positions on the path, he places N targets on which Bessie should try to land (1 <= N <= 1000). Target i is located at position x(i), and is worth p(i) points if Bessie lands on it. Bessie starts at the location of any target of her choosing and is allowed to move in only one direction, hopping from target to target. Each hop must cover at least as much distance as the previous hop, and must land on a target.

Bessie receives credit for every target she touches (including the initial target on which she starts). Please compute the maximum number of points she can obtain.

INPUT FORMAT:

SAMPLE INPUT : 

6
5 6
1 1
10 5
7 6
4 8
8 10

INPUT DETAILS:

There are 6 targets. The first is at position x=5 and is worth 6 points, and so on.

OUTPUT FORMAT:

* Line 1: The maximum number of points Bessie can receive.

SAMPLE OUTPUT :

25

OUTPUT DETAILS:

Bessie hops from position x=4 (8 points) to position x=5 (6 points) to position x=7 (6 points) to position x=10 (5 points). 
출처:usaco/2013NOV/silver
번역:Fate
[질/답] [제출 현황] [푼 후(0)]
[ 채 점 ] [홈으로]  [뒤 로]