← 返回题目列表

AtCoder · abc348_c

F. 七彩豆

中文机器翻译题面 查看原题

分数: 250 点

问题陈述

有 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 is 40.
  • 有两种颜色的豆子 5,美味 20 和 30。因此,在选择颜色时,最低限度的美味 5 is 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