彩色豆子

题目描述

有 $N$ 种豆子,每种各一颗。第 $i$ 种豆子的美味度为 $A_i$,颜色为 $C_i$。这些豆子被混在一起,只能通过颜色区分。

你将选择一种颜色的豆子,并吃掉一颗该颜色的豆子。请选择最优的颜色,使得吃到的豆子的美味度可能达到的最小值最大。

输入格式

输入按以下格式从标准输入给出:

$N$
$A_1$ $C_1$
$A_2$ $C_2$
$\vdots$
$A_N$ $C_N$

输出格式

以整数形式输出吃到的豆子的美味度可能达到的最小值的最大值。

样例

4
100 1
20 5
30 5
40 1

40

注意,同种颜色的豆子彼此无法区分。

你可以选择颜色 $1$ 或颜色 $5$。

颜色 $1$ 有美味度为 $100$ 和 $40$ 的两种豆子,因此选择颜色 $1$ 时,美味度的最小值为 $40$。

颜色 $5$ 有美味度为 $20$ 和 $30$ 的两种豆子,因此选择颜色 $5$ 时,美味度的最小值为 $20$。

为了使美味度的最小值最大,应选择颜色 $1$,此时美味度的最小值为 $40$,故输出 $40$。

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

35

数据范围

• $1 \le N \le 2 \times 10^{5}$
• $1 \le A_i \le 10^{9}$
• $1 \le C_i \le 10^{9}$
• 输入均为整数。