B - Different Distribution

Contest Duration: 2017-09-30(Sat) 12:00 - 2017-09-30(Sat) 13:40 (local time) (100 minutes) Back to Home

B - Different Distribution Editorial

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : $200$ 点

問題文

何人かの人がゲームをしました。全ての人の点数は異なる非負整数でした。

高橋君は、 $N$ 個の情報を持っています。 $i$ 個目の情報は、得点の大きいほうから $A_i$ 番目の人の得点が $B_i$ 点であったことを表します。

ゲームの参加人数としてありうる最大値を求めてください。

制約

$1 \leq N \leq 10^5$
$1 \leq A_i \leq 10^9(1\leq i\leq N)$
$0 \leq B_i \leq 10^9(1\leq i\leq N)$
$i ≠ j$ ならば $A_i ≠ A_j$
与えられる条件すべてを満たす得点の組が存在することが保障される
入力は全て整数である

入力

入力は以下の形式で標準入力から与えられる。

 $N$ 
 $A_1$   $B_1$ 
:
 $A_N$   $B_N$

出力

ゲームの参加人数としてありうる最大値を出力せよ。

入力例 1Copy

Copy

出力例 1Copy

Copy

点数が大きいほうから順に $12,9,8,7,5,2,1,0$ 点である状況が、参加人数の最大値を達成する一例です。

入力例 2Copy

Copy

出力例 2Copy

Copy

入力例 3Copy

Copy

2
1 1000000000
1000000000 1

出力例 3Copy

Copy

1000000001

Score : $200$ points

Problem Statement

A group of people played a game. All players had distinct scores, which are positive integers.

Takahashi knows $N$ facts on the players' scores. The $i$ -th fact is as follows: the $A_i$ -th highest score among the players is $B_i$ .

Find the maximum possible number of players in the game.

Constraints

$1 \leq N \leq 10^5$
$1 \leq A_i \leq 10^9(1\leq i\leq N)$
$0 \leq B_i \leq 10^9(1\leq i\leq N)$
If $i ≠ j$ , $A_i ≠ A_j$ .
There exists a possible outcome of the game that are consistent with the facts.
All input values are integers.

Inputs

Input is given from Standard Input in the following format:

 $N$ 
 $A_1$   $B_1$ 
:
 $A_N$   $B_N$

Outputs

Print the maximum possible number of players in the game.

Sample Input 1Copy

Copy

Sample Output 1Copy

Copy

The maximum possible number of players is achieved when, for example, the players have the following scores: $12,9,8,7,5,2,1,0$ .

Sample Input 2Copy

Copy

Sample Output 2Copy

Copy

Sample Input 3Copy

Copy

2
1 1000000000
1000000000 1

Sample Output 3Copy

Copy

1000000001