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 >= b_i$):
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 <= n <= 150 thin 000$) — the number of potential buyers.
The $i$-th of the next $n$ lines contains two integers $a_i$ and $b_i$ ($0 <= b_i <= a_i <= 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.
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.
## Input
The first line of the input contains an integer $n$ ($1 <= n <= 150 thin 000$) — the number of potential buyers.The $i$-th of the next $n$ lines contains two integers $a_i$ and $b_i$ ($0 <= b_i <= a_i <= 10^9$) — the parameters used in the algorithm of the $i$-th potential buyer.
## Output
Print a single line — the maximum possible total value of sold smartphones.
[samples]
## Scoring
$$ \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.
## Note
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.
**Definitions**
Let $ n \in \mathbb{Z}^+ $ be the number of buyers.
For each buyer $ i \in \{1, \dots, n\} $, let $ a_i, b_i \in \mathbb{Z}_{\geq 0} $ with $ b_i \leq a_i $ be their valuation parameters.
Let $ p_1, p_2 \in \mathbb{Z} $ denote the prices of "Innophone" and "Innophone Plus", respectively, with $ 0 \leq p_1 \leq p_2 $.
Each buyer $ i $ chooses:
- "Innophone Plus" if $ p_2 \leq a_i $ and $ p_2 \leq b_i + (a_i - b_i) \cdot \mathbb{I}_{p_1 > b_i} $,
- "Innophone" if $ p_1 \leq b_i $,
- nothing otherwise.
**Constraints**
1. $ 1 \leq n \leq 150\,000 $
2. $ 0 \leq b_i \leq a_i \leq 10^9 $ for all $ i $
3. $ p_1, p_2 \in \mathbb{Z} $, $ 0 \leq p_1 \leq p_2 $
**Objective**
Maximize the total revenue:
$$
\max_{\substack{p_1, p_2 \in \mathbb{Z} \\ 0 \leq p_1 \leq p_2}} \sum_{i=1}^n
\begin{cases}
p_2 & \text{if } p_2 \leq a_i \text{ and } (p_1 > b_i \text{ or } p_2 \leq b_i) \\
p_1 & \text{if } p_1 \leq b_i \text{ and } (p_2 > a_i \text{ or } p_1 > b_i) \\
0 & \text{otherwise}
\end{cases}
$$
**Simplified Choice Rule (per buyer $ i $):**
Buyer $ i $ selects:
- "Innophone Plus" if $ p_2 \leq a_i $ and $ p_2 \leq a_i $ and $ p_1 > b_i $,
- "Innophone" if $ p_1 \leq b_i $,
- nothing if $ p_1 > b_i $ and $ p_2 > a_i $.
Thus, equivalently:
- If $ p_2 \leq b_i $: buys Plus (since $ p_1 \leq p_2 \leq b_i $)
- Else if $ p_1 \leq b_i < p_2 \leq a_i $: buys Plus
- Else if $ p_1 \leq b_i $ and $ p_2 > a_i $: buys Innophone
- Else if $ b_i < p_1 \leq p_2 \leq a_i $: buys Plus
- Else: buys nothing
But the cleanest formulation is:
Buyer $ i $ buys:
- "Innophone Plus" if $ p_2 \leq a_i $ and $ (p_1 > b_i \text{ or } p_2 \leq b_i) $
- "Innophone" if $ p_1 \leq b_i $ and $ p_2 > a_i $
- Nothing otherwise
Thus, revenue from buyer $ i $:
$$
R_i(p_1, p_2) =
\begin{cases}
p_2 & \text{if } p_2 \leq a_i \text{ and } (p_1 > b_i \text{ or } p_2 \leq b_i) \\
p_1 & \text{if } p_1 \leq b_i \text{ and } p_2 > a_i \\
0 & \text{otherwise}
\end{cases}
$$
**Objective:**
$$
\max_{\substack{p_1, p_2 \in \mathbb{Z} \\ 0 \leq p_1 \leq p_2}} \sum_{i=1}^n R_i(p_1, p_2)
$$