포고 스틱을 단 소

농부 존은 자랑하는 소 베시의 기동력을 높이겠다며 베시의 다리마다 포고 스틱을 달았다. 별로 좋은 생각은 아니었다. 베시는 이제 농장을 빠르게 뛰어다니지만 속도를 줄이는 법은 아직 배우지 못했다.

베시가 도약을 더 정확하게 조절하도록 훈련시키려고, 농부 존은 농장을 가로지르는 직선 경로에 연습 코스를 만들었다. 경로의 서로 다른 위치에 베시가 착지할 표적 $N$개를 놓았다. ($1 \le N \le 1\,000$) $i$번 표적은 위치 $x_i$에 있고, 베시가 여기에 착지하면 $p_i$점을 얻는다.

베시는 원하는 표적 하나를 골라 그 위에서 출발하며, 한 방향으로만 움직이면서 표적에서 표적으로 뛴다. 각 도약은 바로 앞 도약보다 짧으면 안 되고, 반드시 표적 위에 착지해야 한다. 첫 도약에는 거리 제한이 없다.

출발한 표적까지 포함해 베시가 밟은 표적은 모두 점수로 인정된다. 베시가 얻을 수 있는 점수의 최댓값을 구하시오.

첫째 줄에 표적의 개수 $N$이 주어진다. 다음 $N$개 줄 중 $i$번째 줄에는 $i$번 표적의 위치 $x_i$와 점수 $p_i$가 주어진다. 두 값은 모두 $0$ 이상 $1\,000\,000$ 이하의 정수다. 표적의 위치는 서로 다르다.

첫째 줄에 베시가 얻을 수 있는 점수의 최댓값을 출력한다.

예제에서 베시는 위치 $4$에서 출발해 위치 $5$, 위치 $7$, 위치 $10$ 순서로 뛴다. 도약 거리가 $1$, $2$, $3$으로 한 번도 줄어들지 않고, 점수는 $8 + 6 + 6 + 5 = 25$점이다.