Bessie's Pogo Journey

Farmer John has equipped his prize cow Bessie with a pogo stick on each leg. Bessie now hops quickly around the farm, but she has yet to learn how to slow down. To train her to have better control, Farmer John sets up a practice course on a straight one-dimensional path. On this path, there are \(N\) distinct targets. The \(i\)th target is located at position \(x_i\) and is worth \(p_i\) points if Bessie lands on it.

Bessie may choose any target as her starting point, and thereafter she can only move in one direction (to targets with higher positions). When she hops from one target to the next, the distance of the hop must be at least as long as the previous hop's distance. Bessie earns the points of every target she lands on (including the starting target). Your task is to compute the maximum total points Bessie can achieve.

Note: The first hop is free of the distance constraint (i.e. you can consider the initial hop distance as \(0\)).

inputFormat

The first line contains an integer \(N\) (\(1 \le N \le 1000\)) representing the number of targets. The following \(N\) lines each contain two integers \(x_i\) and \(p_i\), where \(x_i\) is the position of the \(i\)th target and \(p_i\) is the points that can be earned at that target.

It is guaranteed that all \(x_i\) are distinct. The targets may be given in any order.

outputFormat

Output a single integer, the maximum total points Bessie can achieve.

sample

3
1 2
3 4
6 5

11