配点: 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