C - Colorful Beans Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 250 点

問題文

N 種類のビーンズが 1 粒ずつあります。 i 種類目のビーンズはおいしさが A_i で色が C_i です。ビーンズは混ぜられており、色でしか区別することができません。

あなたはビーンズの色を 1 つ選び、その色のビーンズをどれか 1 粒食べます。ビーンズの色をうまく選ぶことで、食べる可能性のあるビーンズのおいしさの最小値を最大化してください。

制約

  • 1 \leq N \leq 2 \times 10^{5}
  • 1 \leq A_i \leq 10^{9}
  • 1 \leq C_i \leq 10^{9}
  • 入力は全て整数である。

入力

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

N
A_1 C_1
A_2 C_2
\vdots
A_N C_N

出力

食べる可能性のあるビーンズのおいしさの最小値の最大値を整数として出力せよ。

入力例 1

4
100 1
20 5
30 5
40 1

出力例 1

40

同じ色のビーンズは互いに区別がつかないことに注意してください。

選ぶことができる色は 色 1 と 色 5 です。

  • 色 1 のビーンズは 2 種類あり、美味しさはそれぞれ 100, 40 です。よって、色 1 を選んだときのおいしさの最小値は 40 です。
  • 色 5 のビーンズは 2 種類あり、美味しさはそれぞれ 20, 30 です。よって、色 5 を選んだときのおいしさの最小値は 20 です。

おいしさの最小値を最大化するには 色 1 を選べばよいため、そのときの最小値である 40 を出力します。

入力例 2

10
68 3
17 2
99 2
92 4
82 4
10 3
100 2
78 1
3 1
35 4

出力例 2

35

Score: 250 points

Problem Statement

There are N types of beans, one bean of each type. The i-th type of bean has a deliciousness of A_i and a color of C_i. The beans are mixed and can only be distinguished by color.

You will choose one color of beans and eat one bean of that color. By selecting the optimal color, maximize the minimum possible deliciousness of the bean you eat.

Constraints

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

Input

The input is given from Standard Input in the following format:

N
A_1 C_1
A_2 C_2
\vdots
A_N C_N

Output

Print as an integer the maximum value of the minimum possible deliciousness of the bean you eat.

Sample Input 1

4
100 1
20 5
30 5
40 1

Sample Output 1

40

Note that beans of the same color cannot be distinguished from each other.

You can choose color 1 or color 5.

  • There are two types of beans of color 1, with deliciousness of 100 and 40. Thus, the minimum deliciousness when choosing color 1 is 40.
  • There are two types of beans of color 5, with deliciousness of 20 and 30. Thus, the minimum deliciousness when choosing color 5 is 20.

To maximize the minimum deliciousness, you should choose color 1, so print the minimum deliciousness in that case: 40.

Sample Input 2

10
68 3
17 2
99 2
92 4
82 4
10 3
100 2
78 1
3 1
35 4

Sample Output 2

35