P2352 Duiye's New Book

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$.

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 a single integer ans, the maximum total payment.

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