AT_joi2015ho_d.舞踏会 (Ball)

在 IOI 王国，为了庆祝公主 JOI 的生日，将举办一场舞会。

预计有 $N$ 位贵族参加舞会，$N$ 是奇数。每位贵族编号为 $1$ 到 $N$。每位贵族都有一个表示舞蹈水平的整数，对于贵族 $i$（$1 \leq i \leq N$），其舞蹈水平为 $D_i$。

舞会中，包括 JOI 公主在内的 $N+1$ 个人将两两组队跳舞。在 IOI 王国，为了让高水平者能帮助初学者，传统上采用如下方式决定舞伴：

• 首先，$N$ 位贵族排成一列。
• 只要队列中人数大于 $1$，重复以下操作：
  • 查看队列最前面的 $3$ 位贵族的舞蹈水平。
  • 在这 $3$ 人中，舞蹈水平最高的贵族记为 $A$。若有多人并列，则取编号最小者为 $A$。
  • 在这 $3$ 人中，舞蹈水平最低的贵族记为 $B$。若有多人并列，则取编号最大者为 $B$。
  • $A$ 与 $B$ 组成一组并离开队列。
  • 剩下的那个人移动到队列末尾。
• 最终剩下的 $1$ 人将与 JOI 公主组队。

对于编号 $1$ 到 $M$（$1 \leq M \leq N-2$）的 $M$ 位贵族，他们在初始队列中的位置已确定。剩下的 $N-M$ 位贵族的排列顺序由国王自由决定。

JOI 公主刚刚学会跳舞，因此国王希望能让与 JOI 公主组队的贵族的舞蹈水平尽可能高。请你求出 JOI 公主最终可能组队的贵族的舞蹈水平的最大值。

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

• 第 $1$ 行包含两个整数 $N, M$，表示参加舞会的贵族人数和初始队列中位置已确定的贵族人数。
• 接下来 $M$ 行，第 $i$ 行（$1 \leq i \leq M$）包含两个整数 $D_i, P_i$，表示贵族 $i$ 的舞蹈水平为 $D_i$，且初始时排在队列第 $P_i$ 个位置。
• 接下来 $N-M$ 行，第 $i$ 行（$1 \leq i \leq N-M$）包含一个整数 $D_{i+M}$，表示贵族 $i+M$ 的舞蹈水平为 $D_{i+M}$。

输出一个整数，表示 JOI 公主最终可能组队的贵族的舞蹈水平的最大值。

任务

给定每位贵族的舞蹈水平和 $M$ 位贵族的初始队列位置，编写程序求出 JOI 公主最终可能组队的贵族的舞蹈水平的最大值。

限制

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

• $3 \leq N \leq 99\,999$。
• $N$ 是奇数。
• $1 \leq M \leq N-2$。
• $1 \leq D_i \leq 1\,000\,000\,000$（$1 \leq i \leq N$）。
• $1 \leq P_i \leq N$（$1 \leq i \leq M$）。
• $P_i \neq P_j$（$1 \leq i < j \leq M$）。

子任务

子任务 1 [8 分]

• 满足 $N \leq 9$。

子任务 2 [16 分]

• 满足 $N \leq 19$。

子任务 3 [44 分]

• 满足 $N \leq 1\,999$。

子任务 4 [32 分]

无额外限制。

样例解释 1

初始时有 $3$ 位贵族的位置已确定。

括号内的数字表示舞蹈水平。左端为队列前端。
例如，若队列顺序为贵族 $5$，贵族 $1$，贵族 $4$，贵族 $6$，贵族 $2$，贵族 $3$，贵族 $7$，则：

所有贵族排好队后的顺序如下：

此时队列变化如下：

• 队列前 $3$ 人（贵族 $5$，$1$，$4$）中，舞蹈水平最高的是贵族 $4$，最低的是贵族 $5$，于是 $4$ 和 $5$ 组队，剩下的贵族 $1$ 移到队尾。
• 接着，队列前 $3$ 人（贵族 $6$，$2$，$3$）中，舞蹈水平最高的是贵族 $6$ 和 $3$，取编号较小的贵族 $3$，最低的是贵族 $2$，于是 $3$ 和 $2$ 组队，剩下的贵族 $6$ 移到队尾。
• 接着，队列前 $3$ 人（贵族 $7$，$1$，$6$）中，舞蹈水平最高的是贵族 $7$，最低的是贵族 $1$，于是 $7$ 和 $1$ 组队，剩下的贵族 $6$ 移到队尾。
• 最终只剩贵族 $6$，与 JOI 公主组队。贵族 $6$ 的舞蹈水平为 $8$，这是 JOI 公主可能组队的贵族舞蹈水平的最大值。

队列变化过程示意图。

样例解释 2

无论如何排列，最终都是贵族 $2$ 与 JOI 公主组队。

由 ChatGPT 4.1 翻译