3.3 The Missing MasterMind

Score: 20pts

Time Limit: 2.00 sec

Harsh was stuck at his desk, staring at the job scheduling problem. Deadlines loomed, and profits were at stake. No matter how much he tried, he couldn’t figure out how to maximize the profits within the time limits. Frustrated, he muttered, "Danish Bhai agar zinda hota na toh solve kar lete." Danish was the mastermind in their circle, always picking the right tasks at the right time to get the best results. Harsh sighed, thinking about how Danish would’ve effortlessly picked jobs and squeezed every last bit of profit from the chaos.

Note: Each Job takes one time interval only.

Note: Each Job takes one time interval only.

Constraints

1 <= N <= 10^5 1<= p,d <= 10^9

Input Format

The first line contains a single integer N, the number of jobs and the total time available for job sequencing .Each of the next N lines contains two integers, d (the deadline) and p (the profit), for each job, where d is the deadline and p is the profit.

Output Format

A single integer, the maximum total profit by completing the optimal set of jobs.

Example 1

Input:

5

2 100

1 50

2 200

1 20

3 300

Output:

600

Explanation:

For a total time interval of 5 and 5 jobs with their respective deadline time intervals the optimal profit is = 600.

Note: Each job takes 1 time interval only

5

2 100

1 50

2 200

1 20

3 300

Output:

600

Explanation:

For a total time interval of 5 and 5 jobs with their respective deadline time intervals the optimal profit is = 600.

Note: Each job takes 1 time interval only