#T646. OJ作业

OJ作业

Description

When registering a CodesOnline account, the system automatically schedules all OJ problems. For each OJ problem, OJ points are only awarded if the submission is made within the specified time limit. The deadline and OJ points for each problem may vary. For example, if an OJ problem offers 10 points and requires submission within 6 days, you must submit it before the end of the 6th day to earn the 10 points.

Each problem takes exactly one day to complete. For instance, consider the following 7 problems with their respective deadlines and OJ points:

Problem ID Deadline OJ Points
1 1 6
2 1 7
3 3 2
4 3 1
5 2 4
6 2 5
7 6 1

The maximum achievable points here are 15. One possible order of completion is: 2, 6, 3, 1, 7, 5, 4. Note that other valid sequences may also yield the same result.

Your task is to determine an optimal order for completing the problems to maximize the total OJ points earned.

Input Format

The first line contains an integer X, representing the number of problems.

The next X lines each contain two integers: the first integer denotes the problem's deadline, and the second integer represents its OJ points.

Output Format

Output a single integer representing the maximum achievable points. It is guaranteed that the answer does not exceed the range of int in C/C++.

```input1 7 1 6 1 7 3 2 3 1 2 4 2 5 6 1 ``` ```output1 15 ``` ## Hint

【Data Range】

For 20% of the data, X ≤ 10^3;

For 40% of the data, X ≤10^4;

For 60% of the data, X ≤10^5;

For 100% of the data, X ≤10^6, and the completion deadlines for all problems are less than 7×10^5.


Source

Adapted from "Olympiad Tutorial" textbook