- Time limit: 1.00 s
- Memory limit: 512 MB
You have to process tasks. Each task has a duration and a deadline, and you will process the tasks in some order one after another. Your reward for a task is where is its deadline and is your finishing time. (The starting time is , and you have to process all tasks even if a task would yield negative reward.)
What is your maximum reward if you act optimally?
Input
The first input line has an integer : the number of tasks.
After this, there are lines that describe the tasks. Each line has two integers and : the duration and deadline of the task.
Output
Print one integer: the maximum reward.
Constraints
Example
Input:
3 6 10 8 15 5 12
Output:
2