Description

Duiye is about to publish a new book to record his glorious problem-solving journey.

There are $n$ publishers interested in this book. Each is willing to pay a fee $p \in [Min_{pay}, Max_{pay}]$ to obtain the publishing rights, where each publisher has its own $Min_{pay}$ and $Max_{pay}$.

Now Duiye wants you to find a value $p$ that maximizes his total revenue. Every publisher with $Min_{pay} \leq p \leq Max_{pay}$ will pay $p$.

Input Format

The first line contains an integer $n$.

The next $n$ lines each contain two integers $Min_{payi}$ and $Max_{payi}$, which are the acceptable payment range of the $i$-th publisher.

Output Format

Output a single integer ans, the maximum total payment.

4
1 3
2 4
3 5
4 7

12

Hint

Sample Explanation:

When $p = 4$, there are $3$ publishers who will pay, which is maximal.

Constraints:

• For $20\%$ of the testdata, $1 \leq Min_{pay}, Max_{pay} \leq 10000$.
• For $40\%$ of the testdata, $1 \leq n \leq 1000, 1 \leq Min_{pay}, Max_{pay} \leq 10^6$.
• For $100\%$ of the testdata, $1 \leq n \leq 100000, 1 \leq Min_{pay}, Max_{pay} \leq 10^9$.

Translated by ChatGPT 5