405880: GYM102147 B Innophone

Some telecommunications company plans to simultaneously introduce two innovative smartphones to the market. These smartphones will be called ,,Innophone" and ,,Innophone Plus". The devices are ready for production, but there is one more thing the company management needs to decide about – the optimal price for each type of smartphone.

The company hired analysts to analyze the market. They conducted a study in which they built the following model. There are $$$n$$$ potential buyers of innovative smartphones. The $$$i$$$-th buyer uses the following algorithm, characterized by two numbers $$$a_i$$$ and $$$b_i$$$ ($$$a_i \geq b_i$$$):

• If the price of ,,Innophone Plus" is at most $$$a_i$$$, he buys ,,Innophone Plus".
• Otherwise, if the price of ,,Innophone" is at most $$$b_i$$$, he buys ,,Innophone".
• Otherwise, he doesn't buy anything.

The company wants to set the prices of ,,Innophone" and ,,Innophone Plus" in such a way that both prices are integers, the price of ,,Innophone" is not greater than the price of ,,Innophone Plus", and the total value of sold phones is the highest.

Write a program that finds the maximum possible total value of the sold smartphones, i.e. the total amount of money the buyers will pay.

The first line of the input contains an integer $$$n$$$ ($$$1 \leq n \leq 150\,000$$$) — the number of potential buyers.

The $$$i$$$-th of the next $$$n$$$ lines contains two integers $$$a_i$$$ and $$$b_i$$$ ($$$0 \leq b_i \leq a_i \leq 10^9$$$) — the parameters used in the algorithm of the $$$i$$$-th potential buyer.

Print a single line — the maximum possible total value of sold smartphones.

$$$$$$ \begin{array}{|c|c|c|c|} \hline \text{Subtask} & \text{Points} & \text{Constraints} & \text{Dependencies} \\ \hline 1 & 9 & n \le 100; b_i \le a_i \le 100 & 0 \\ \hline 2 & 10 & n \le 300 & 0, 1 \\ \hline 3 & 16 & n \le 3000 & 0, 1, 2 \\ \hline 4 & 11 & n \le 10^5; b_i = 0 & \\ \hline 5 & 16 & n \le 10^5; a_i = b_i & \\ \hline 6 & 7 & n \le 50\,000 & 0 - 3 \\ \hline 7 & 7 & n \le 75\,000 & 0 - 3, 6 \\ \hline 8 & 8 & n \le 100\,000 & 0 - 7 \\ \hline 9 & 8 & n \le 125\,000 & 0 - 8 \\ \hline 10 & 8 & n \le 150\,000 & 0 - 9 \\ \hline \end{array}$$$$$$

You will get points for a group if you pass all tests in this group and all groups listed in the dependencies. The group $$$0$$$ denotes the sample test(s) from the statement.

5
80 20
60 50
40 40
15 10
70 30

220

1
50 0

50

In the first sample test, the optimal prices of ,,Innophone" and ,,Innophone Plus" are $$$40$$$ and $$$70$$$ respectively. The first and fifth buyer will buy ,,Innophone Plus", while the second and third buyer will buy ,,Innophone". The fourth buyer will not buy anything. The total value of sold smartphones is then $$$70+40+40+0+70=220$$$.

In the second sample test, you need to set the price of ,,Innophone Plus" to $$$50$$$. The price of ,,Innophone" doesn't matter.