Under construction

Still being built. Things may change

Consultations before resignation

Interview

Time limit2sMemory limit512 MB

Summary
Given up to 1.5 million days, each with a job of length T_i and pay P_i, pick jobs that fit before day N+1 to maximize total pay.
Level

Medium5 of 10

Topics
Dynamic programming, Array, Greedy, Implementation
Solved
No attempts yet

Problem

Minjun works as a consultant and is preparing to resign.

He leaves on day N+1 counting from today, so he wants to handle as many consultations as he can during the N days that remain.

Minjun asked his secretary to book as many consultations as possible, and she booked one consultation per day, each with a different client.

Every consultation has a duration TiT_i, the number of days it takes to finish, and a payment PiP_i, the amount he receives once it is done.

Look at the schedule for N = 7.

Day 1Day 2Day 3Day 4Day 5Day 6Day 7
TiT_i3511242
PiP_i102010201540200

The consultation booked on day 1 takes 3 days and pays 10. The consultation booked on day 5 takes 2 days and pays 15.

A single consultation can take longer than one day, so he cannot handle all of them. For example, if he starts the consultation on day 1, he cannot handle the ones on days 2 and 3. If he starts the one on day 2, he cannot handle the ones booked on days 3, 4, 5 and 6.

He is also not at the company on day N+1, so he cannot handle the consultations on days 6 and 7.

The largest profit before he resigns comes from handling the consultations on days 1, 4 and 5, and that profit is 10+20+15=45.

Write a program that computes the largest profit Minjun can earn by choosing the consultations well.

Input

The first line contains N (1≤N≤15000001 \le N \le 1500000).

Each of the next N lines contains TiT_i and PiP_i separated by a space, given in order from day 1 to day N. (1≤Ti≤501 \le T_i \le 50, 1≤Pi≤10001 \le P_i \le 1000)

Output

Print the largest profit Minjun can earn on the first line.

Examples5

  1. Example 1

    Input
    7
3 10
5 20
1 10
1 20
2 15
4 40
2 200
    Expected output
    45

  2. Example 2

    Input
    10
1 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
    Expected output
    55

  3. Example 3

    Input
    10
5 10
5 9
5 8
5 7
5 6
5 10
5 9
5 8
5 7
5 6
    Expected output
    20

  4. Example 4

    Input
    10
5 50
4 40
3 30
2 20
1 10
1 10
2 20
3 30
4 40
5 50
    Expected output
    90

  5. Example 5

    Input
    1
1 1000
    Expected output
    1000