408008: GYM102961 V Tasks and Deadlines

You have to process $$$n$$$ 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 $$$d−f$$$ where $$$d$$$ is its deadline and $$$f$$$ is your finishing time. (The starting time is $$$0$$$, and you have to process all tasks even if a task would yield negative reward.)

What is your maximum reward if you act optimally?

The first input line has an integer $$$n$$$: the number of tasks.

After this, there are $$$n$$$ lines that describe the tasks. Each line has two integers $$$a$$$ and $$$d$$$: the duration and deadline of the task.

Constraints:

• $$$1 \le n \le 2\cdot 10^5$$$
• $$$1 \le a,d \le 10^6$$$

Print one integer: the maximum reward.

3
6 10
8 15
5 12

2