Lecture Tour

Interview

Time limit2sMemory limit128 MB

Summary
Given jobs each with a fee and a deadline, schedule at most one job per day to maximize total fee collected before deadlines.
Level

Medium6 of 10

Topics
Greedy, Union-find, Sorting
Solved
No attempts yet

Problem

An academic has received lecture requests from n universities, where 0 ≤ n ≤ 10,000. Each university offers a fee p, where 1 ≤ p ≤ 10,000, if the lecture is given within d days, where 1 ≤ d ≤ 10,000. The values p and d may differ for each university.

The academic can give at most one lecture per day. Determine the maximum total fee the academic can earn.

Input

The first line contains the integer n. Each of the next n lines contains two integers p and d, the offered fee and the deadline in days.

Output

Print the maximum total fee that can be earned.

Examples1

  1. Example 1

    Input
    7
20 1
2 1
10 3
100 2
8 2
5 20
50 10
    Expected output
    185