Background

Translated from ROI 2018 Day1 T3. Иннофон (Innophone)。

Problem Description

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.

Input Format

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 Format

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

5
80 20
60 50
40 40
15 10
70 30

220

1
50 0

50

Hint

For $100\%$ of the testdata, $0\leq y_i\leq x_i\leq 10^9$, $1 \leq n \leq 1.5 \times 10^5$.

Translated by ChatGPT 5