Description

{{We have many talks to be held in a lecture hall. Each talk is determined by a unique start time and end time. If two talks overlap partially or entirely, they cannot be held simultaneously in the lecture hall. We want to make the best possible use of this hall; that is, we need to select some non-overlapping talks so that their total scheduled time is as long as possible. We assume that at the exact moment one talk ends, another talk can start immediately.

Write a program to:

Read all start and end times of the talks and compute the maximum possible total time of talks.}}

Input Format

{{The first line contains a positive integer $n$, the number of talks.

Each of the following $n$ lines contains two space-separated integers $p$ and $k$. Such a pair indicates a talk that starts at time $p$ and ends at time $k$.}}

Output Format

{{Output a single integer, the maximum total time of the talks.}}

12
1 2
3 5
0 4
6 8
7 13
4 6
9 10
9 12
11 14
15 19
14 16
18 20

16

Hint

{{Sample Explanation

You can choose the 3rd, 5th, 6th, 11th, and 12th talks, yielding the maximum total duration $16$.

Constraints

$1 \le n \le 10^4$, $0 \le p < k \le 3 \times 10^4$.}}

Translated by ChatGPT 5