Brick Tower

Xiao Ming is moving bricks. He has n bricks. The i^th brick has a weight \(w_{i}\) and a value \(v_{i}\). He wants to select some of these bricks and stack them from bottom to top to form a tower. The constraint is that for every brick in the tower, the total weight of all bricks above it must not exceed its own value. In other words, if a brick with parameters \(w\) and \(v\) is placed in the tower and the total weight of all bricks stacked above it is \(W_{above}\), then it must satisfy:

[ W_{above} \le v ]

The goal is to construct such a tower with the maximum total value (i.e. the sum of the values \(v\) of the bricks in the tower).

inputFormat

The first line contains a single integer \(n\), the number of bricks.

Each of the following \(n\) lines contains two integers \(w_{i}\) and \(v_{i}\), representing the weight and value of the \(i\)^th brick.

outputFormat

Output a single integer, the maximum total value of bricks that can be used to build a valid tower.

sample

2
1 1
2 2

2