Consultations before resignation

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 $T_i$ , the number of days it takes to finish, and a payment $P_i$ , the amount he receives once it is done.

Look at the schedule for N = 7.

	Day 1	Day 2	Day 3	Day 4	Day 5	Day 6	Day 7
$T_i$	3	5	1	1	2	4	2
$P_i$	10	20	10	20	15	40	200

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 \le N \le 1500000$ ).

Each of the next N lines contains $T_i$ and $P_i$ separated by a space, given in order from day 1 to day N. ( $1 \le T_i \le 50$ , $1 \le P_i \le 1000$ )

Output

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