Supermarket

A supermarket has products that may each be sold at most once. Product i earns profit p_i if its one-unit sale finishes no later than deadline d_i. A selling schedule is any ordered subset meeting every selected product's deadline. Find the maximum total profit.

Input

The input contains multiple data sets and ends at end of file. A data set begins with n (0 \le n \le 10000), followed by n pairs p_i,d_i, where 1 \le p_i,d_i \le 10000. Whitespace may occur freely.

Output

For each data set, print the maximum possible profit on its own line.

Example

Input:

4 50 2 10 1 20 2 30 1
7 20 1 2 1 10 3 100 2 8 2 5 20 50 10

Output:

80
185