Bob's Function

View as PDF

Submit solution

Points: 17 (partial)
Time limit: 2.0s
Memory limit: 512M

Problem types

Bob has a function f(x, y), which is defined as follows

\displaystyle 
  f(x, y) =
    \begin{cases}
      a & \text{if } a \le x\\
      b & \text{else if } b \le y\\
      0 & \text{else}
    \end{cases}       
where a, b are constants.

Bob has N pairs of x_i and y_i (0 \le y_i \le x_i \le 10^9). Bob wants to find some constants a and b so that he can maximize \sum_{i=1}^{N} { f(x_i, y_i) }. Can you help him find out the max possible sum?

Input Specification

The first line of input contains one integer N, (1 \le N \le 150\,000), the number of pairs x and y.

Each of the following N lines contains two integers x_i and y_i, (0 \le y_i \le x_i \le 10^9).

Output Specification

Output one integer, the maximum \sum_{i=1}^{N} { f(x_i, y_i) }.

Constraints

For all test cases, 0 \le y_i \le x_i \le 10^9.

Subtask Points Additional constraints
1 9 N \le 100 and x_i \le 100
2 10 N \le 300
3 16 N \le 3000
4 11 N \le 10^5 and y_i = 0
5 16 N \le 10^5 and y_i = x_i
6 14 N \le 7.5 \times 10^4
7 24 No additional constraints.

Sample Input 1

1
50 0

Sample Output 1

50

Explanation

One possible pair of a and b is (50, 0).

Sample Input 2

5
80 20
60 50
40 40
15 10
70 30

Sample Output 2

220

Explanation

One possible pair of a and b is (60, 40).

  • For x=80, y = 20, since a <= x, f(x, y) = a, which is 60
  • For x=60, y = 50, since a <= x, f(x, y) = a, which is 60
  • For x=40, y = 40, since a > x and b <=y, f(x, y) = b, which is 40
  • For x=15, y = 10, since a > x and b > y, f(x, y) = 0
  • For x=70, y = 30, since a <= x, f(x, y) = a, which is 60

Thus, the total sum is 60 + 60 + 40 + 0 + 60 = 220. It's the maximum possible sum.


Comments

There are no comments at the moment.