C - Absolute Ace Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 333 点

問題文

高橋君はサッカーチームの監督です。チームには N 人の選手がおり、選手 i (1 \leq i \leq N) は攻撃力 A_i と守備力 B_i の 2 つのパラメータを持っています。

ある選手 k が絶対的エースであるとは、k 以外のすべての選手 j (1 \leq j \leq N, j \neq k) に対して、A_k > A_j かつ B_k > B_j が成り立つことを指します。

高橋君は、特別な強化トレーニングを繰り返し行うことができます。1 回のトレーニングでは、N 人の中から選手を 1 人選び、その選手の攻撃力と守備力のうちちょうど 1 つを選んで 1 だけ上昇させます。同じ選手を何度でも選ぶことができ、同じパラメータを何度でも上昇させることができます。また、異なる選手に対してそれぞれトレーニングを行うこともできます。ただし、パラメータを下げることはできません。トレーニングを 1 回も行わないことも許されます。

高橋君は、すべてのトレーニングが終了した後の状態において、絶対的エースである選手が少なくとも 1 人存在するようにしたいと考えています。絶対的エースとなる選手は N 人のうち誰であってもかまいません。この状態を達成するために必要なトレーニングの最小回数を求めてください。

制約

  • 2 \leq N \leq 2 \times 10^5
  • 1 \leq A_i \leq 10^9
  • 1 \leq B_i \leq 10^9
  • 入力はすべて整数である。

入力

N
A_1 B_1
A_2 B_2
\vdots
A_N B_N
  • 1 行目には、選手の人数を表す整数 N が与えられる。
  • 続く N 行の i 行目 (1 \leq i \leq N) には、選手 i の攻撃力 A_i と守備力 B_i がスペース区切りで与えられる。

出力

絶対的エースである選手が少なくとも 1 人存在する状態を達成するために必要なトレーニングの最小回数を 1 行で出力せよ。

入力例 1

3
3 1
1 3
2 2

出力例 1

3

入力例 2

5
10 10
3 5
7 2
1 8
5 5

出力例 2

0

入力例 3

7
5 8
9 3
7 7
4 6
8 5
6 9
3 4

出力例 3

4

Score : 333 pts

Problem Statement

Takahashi is the manager of a soccer team. The team has N players, and player i (1 \leq i \leq N) has two parameters: attack power A_i and defense power B_i.

A player k is called an absolute ace if, for every other player j (1 \leq j \leq N, j \neq k), both A_k > A_j and B_k > B_j hold.

Takahashi can repeatedly conduct special training sessions. In one training session, he selects one player from the N players, chooses exactly one of that player's attack power or defense power, and increases it by 1. The same player can be selected any number of times, and the same parameter can be increased any number of times. Training can also be performed on different players. However, parameters cannot be decreased. It is also allowed to perform no training sessions at all.

Takahashi wants to ensure that, after all training sessions are completed, there exists at least one player who is an absolute ace. The absolute ace can be any of the N players. Find the minimum number of training sessions required to achieve this.

Constraints

  • 2 \leq N \leq 2 \times 10^5
  • 1 \leq A_i \leq 10^9
  • 1 \leq B_i \leq 10^9
  • All input values are integers.

Input

N
A_1 B_1
A_2 B_2
\vdots
A_N B_N
  • The first line contains an integer N representing the number of players.
  • The i-th of the following N lines (1 \leq i \leq N) contains the attack power A_i and defense power B_i of player i, separated by a space.

Output

Print in one line the minimum number of training sessions required to achieve a state where at least one player is an absolute ace.

Sample Input 1

3
3 1
1 3
2 2

Sample Output 1

3

Sample Input 2

5
10 10
3 5
7 2
1 8
5 5

Sample Output 2

0

Sample Input 3

7
5 8
9 3
7 7
4 6
8 5
6 9
3 4

Sample Output 3

4