Maximize Sum of a Piecewise Function

Given a binary function \( f(x,y) \) defined as follows:

\[ f(x,y)=\begin{cases} a, & \text{if } a \le x,\\ b, & \text{else if } b \le y,\\ 0, & \text{otherwise}, \end{cases} \]

where \(a\) and \(b\) are constants, and given \(n\) pairs \( (x_i,y_i) \) for \(i=1,2,\dots,n\), choose appropriate values of \(a\) and \(b\) so that the sum

\[ S = \sum_{i=1}^{n} f(x_i,y_i) \]

is maximized. In other words, for each pair \( (x_i,y_i) \), if \(x_i \ge a\) then it contributes \(a\) to the sum; otherwise, if \(y_i \ge b\) then it contributes \(b\); else it contributes \(0\). Output the maximum possible sum.

inputFormat

The first line contains a single integer \(n\) \( (1 \le n \le 10^5) \) indicating the number of pairs.

Each of the next \(n\) lines contains two integers \(x\) and \(y\), representing a pair \( (x,y) \). It is guaranteed that the input numbers are such that an optimal solution exists within the search space defined by \(x\) and \(y\) values.

outputFormat

Output a single integer representing the maximum sum \(S\) that can be obtained by choosing appropriate values of \(a\) and \(b\) according to the given function.

sample

3
1 2
2 1
3 4

6