103482: [Atcoder]ABC348 C - Colorful Beans

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

问题描述

有$N$种豆子，每种各有一颗。第$i$种豆子的美味度为$A_i$，颜色为$C_i$。豆子已经混合，只能通过颜色来区分。

你将选择一种颜色的豆子并吃掉一颗。通过选择最优的颜色，使你吃到的豆子的最小可能美味度最大化。

限制条件

• $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$的豆子，美味度分别为$100$和$40$。因此，选择颜色$1$时的最小美味度是$40$。
• 有两颗颜色为$5$的豆子，美味度分别为$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