P9288 [ROI 2018] Innophone

Translated from [ROI 2018 Day1](https://neerc.ifmo.ru/school/archive/2017-2018.html) T3. [Иннофон](https://neerc.ifmo.ru/school/archive/2017-2018/ru-olymp-roi-2018-day1.pdf) ([Innophone](http://codeforces.com/gym/102147/problem/B))。

There is a binary function $f(x,y)$ defined as follows: $ f(x,y)=\left\{ \begin{array}{rcl} a, & & {\text{if} \quad \quad \ \ \ a \leq x}\\ b, & & {\text{else if} \quad b \leq y}\\ 0, & & {\text{else}} \end{array} \right.$ Here $a,b$ are constants. You are given $n$ pairs $(x,y)$. You need to choose suitable $a,b$ so that $\sum_{i=1}^{n} f(x_i,y_i)$ is maximized.

The first line contains an integer $n$, the number of pairs $(x,y)$. The next $n$ lines each contain two numbers $x_i$ and $y_i$.

Output one number on one line: $\max(\sum_{i=1}^{n} f(x_i,y_i))$.

For $100\%$ of the testdata, $0\leq y_i\leq x_i\leq 10^9$, $1 \leq n \leq 1.5 \times 10^5$. | Subtask ID | $n$ | $x,y$ | | :----------: | :----------: | :----------: | | $1$ | $1 \leq n \leq 100$ | $0 \leq y_i \leq x_i \leq 100$ | | $2$ | $1 \leq n \leq 300$ | $0\leq y_i\leq x_i\leq 10^9$ | | $3$ | $1 \leq n \leq 3000$ | $0\leq y_i\leq x_i\leq 10^9$ | | $4$ | $1 \leq n \leq 10^5$ | $y_i = 0$ | | $5$ | $1 \leq n \leq 10^5$ | $x_i = y_i$ | | $6$ | $1 \leq n \leq 50000$ | $0\leq y_i\leq x_i\leq 10^9$ | | $7$ | $1 \leq n \leq 75000$ | $0\leq y_i\leq x_i\leq 10^9$ | | $8$ | $1 \leq n \leq 10^5$ | $0\leq y_i\leq x_i\leq 10^9$ | | $9$ | $1 \leq n \leq 1.25 \times 10^5$ | $0\leq y_i\leq x_i\leq 10^9$ | | $10$ | $1 \leq n \leq 1.5 \times 10^5$ | $0\leq y_i\leq x_i\leq 10^9$ | Translated by ChatGPT 5