← 返回题目列表

AtCoder · joi2015ho_d

D. 球

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

配点: 100 点

在IOI王国,将举行舞会来庆祝公主JOI公主的生日。

在舞会上 N 贵族预定参加。N 是奇数。对于贵族来说 它们的编号最大为 1 从 N 。每个贵族都会被分配一个整数来表示舞者的水平。 i (1 \leqq i \leqq N) 的舞蹈技巧是 D_i 。

包括舞会上的 JOI 公主 N + 1 在人中 2 人们分组跳舞。在IOI王国,舞蹈组传统上是按以下方式确定的,以便高级舞者可以帮助初学者。

  • 首先,N 贵族 1 排队。
  • 贵族们排队 1 重复以下操作,直到有一个人。
    • 从专栏开始 3 看看一个人的贵族舞蹈水平如何。
    • 那 3 在所有贵族中,选择最擅长跳舞的人。 A 。但是,如果有多于一名,则选择舞蹈技能最好的人数最少的一名。 A 。
    • 那 3 在所有贵族中,选择舞蹈技能最少的一位。 B 。但是,如果有多个贵族,则选择舞蹈技能最少的贵族中数量最多的贵族。 B 。
    • A 和 B 离开序列并成为一对。
    • 仍然存在 1 此人移至行尾。
  • 最后还剩下什么 1 一个人与一个JOI公主配对。贵族 1 来自贵族 M (1 \leqq M \leqq N - 2) 的 M 对于每个贵族来说,在初始状态下在队列中的位置就已经确定了。其余的 N - M 国王可以自由决定贵族的排列方式。

由于JOI公主刚刚学会跳舞,国王希望尽可能提高与JOI公主配对的贵族们的舞蹈技巧。 JOI 找出与公主配对的贵族的舞蹈技能的最大值。

課題

各个贵族的舞蹈技巧,M 给定一组贵族在初始状态下排队的位置,编写一个程序来找到将与 JOI 公主配对的贵族的舞蹈技能的最大值。


入力

从标准输入读取以下数据。 在

  • 1 行中,2 整数 给出了 N, M 以空格作为分隔符。这是舞会上的贵族。 N 已经决定排队的贵族 M 表示有人。
  • 继续 来自行 M 行 i 行目 (1 \leqq i \leqq M)有2 整数 给出了 D_i, P_i 以空格作为分隔符。这就是贵族 i 的舞蹈技巧 D_i ,贵族 i 是初始状态,从列的开头开始。 代表第 P_i 行。
  • 继续 来自行 N - M 行 i 行目 (1 \leqq i \leqq N - M) 是一个整数 写入 D_{i + M} 。这是一个贵族(i + M) 娴熟的舞姿 D_{i + M} 。

出力

代表将与 JOI 公主配对的贵族的最大可能舞蹈技能的整数被发送到标准输出。 输出为 1 行。


制限

所有输入数据满足以下条件。

  • 3 \leqq N \leqq 99\,999.
  • N 是奇数。
  • 1 \leqq M \leqq N - 2.
  • 1 \leqq D_i \leqq 1\,000\,000\,000 (1 \leqq i \leqq N).
  • 1 \leqq P_i \leqq N (1 \leqq i \leqq M).
  • P_i \neq P_j (1 \leqq i < j \leqq M).

小課題

小課題 1 [8 点]

  • N \leqq 9 很满意。

小課題 2 [16 点]

  • N \leqq 19 很满意。

小課題 3 [44 点]

  • N \leqq 1\,999 很满意。

小課題 4 [32 点]

没有其他限制。


入力例 1

7 3
5 2
5 5
8 6
6
2
8
9

出力例 1

8

初始状态 3 贵族们排队的地方已经决定了。

括弧内の数字は踊りのうまさを表す.左端が列の先頭である.

比如,从一开始,贵族 考虑它们按 5,貴族 1,貴族 4,貴族 6,貴族 2,貴族 3,貴族 7 顺序排列的情况。

すべての貴族が並んだあとの配置

在这种情况下,列将发生如下变化。

  • 在栏的开头 3 贵族(贵族) 5,貴族 1,貴族 4) 其中,最擅长跳舞的是贵族。 4 还有跳舞能力最差的贵族。 5 已配对,其余贵族 1 移至末尾。
  • 接下来,在专栏的开头 3 贵族(贵族) 6,貴族 2,貴族 3),跳得最好的贵族就是贵族。 6 和贵族 3 的 2 编号最低的贵族为贵族。 3 。另外,在专栏的开头 3 人类贵族中,舞蹈功底最差的就是贵族。 2 。贵族 3 和贵族 2 已配对,其余贵族 6 移至末尾。
  • 接下来,在专栏的开头 3 贵族(贵族) 7,貴族 1,貴族 6),最擅长跳舞的贵族。 7 还有跳舞能力最差的贵族。 1 已配对,其余贵族 6 移至末尾。
  • 终于贵族了 6 保留并与 JOI Princess 配对。贵族 6 的舞蹈技巧是 8 。这个值是可以认为是与JOI公主配对的贵族舞蹈技能的最大值。

列の変化の様子


入力例 2

3 1
5 3
5
5

出力例 2

5

无论你排队什么顺序,贵族 2 和JOI公主配对在一起。


入力例 3

7 2
32 4
27 6
37
41
41
30
27

出力例 3

37