P15819 [JOI 2015 Final] 舞会 / Ball

在 IOI 王国，为了庆祝公主 JOI 姬的生日，将举办一场舞会。 舞会预计有 $N$ 位贵族参加。$N$ 是奇数。贵族们被编号为 $1$ 到 $N$。每位贵族都有一个被称为“舞蹈技巧”的整数值，贵族 $i$ ($1 \le i \le N$) 的舞蹈技巧为 $D_i$。 舞会上，包括 JOI 姬在内的 $N+1$ 人将两两配对跳舞。在 IOI 王国，为了能让资深者辅助初学者，传统上按以下方法决定舞蹈配对： * 首先，$N$ 位贵族排成一列。 * 重复以下操作，直到队列中只剩下一人： * 检查队列最前面三位贵族的舞蹈技巧。 * 在这三位贵族中，将舞蹈技巧**最大**的贵族记为 A。如果有多个舞蹈技巧最大的贵族，则取其中**编号最小**的贵族作为 A。 * 在这三位贵族中，将舞蹈技巧**最小**的贵族记为 B。如果有多个舞蹈技巧最小的贵族，则取其中**编号最大**的贵族作为 B。 * A 和 B 离开队列，组成一对。 * 剩下的一位贵族移动到队列的末尾。 * 最后剩下的那一位贵族将与 JOI 姬组成一对。 对于贵族 1 到贵族 $M$ ($1 \le M \le N-2$) 这 $M$ 位贵族，他们在初始队列中的位置已经确定。剩下的 $N-M$ 位贵族的排列顺序可以由国王自由决定。 JOI 姬刚开始学习跳舞，因此国王希望与 JOI 姬配对的贵族的舞蹈技巧尽可能大。请求出与 JOI 姬配对的贵族的舞蹈技巧可能达到的最大值。 ### 任务 给定每位贵族的舞蹈技巧以及 $M$ 位贵族在初始队列中的位置，请编写一个程序，计算与 JOI 姬配对的贵族的舞蹈技巧可能达到的最大值。

从标准输入读取以下数据。 * 第一行包含两个以空格分隔的整数 $N, M$。这表示舞会有 $N$ 位贵族参加，且队列中已有 $M$ 位贵族的位置被确定。 * 接下来的 $M$ 行中，第 $i$ 行 ($1 \le i \le M$) 包含两个以空格分隔的整数 $D_i, P_i$。这表示贵族 $i$ 的舞蹈技巧为 $D_i$，且他在初始队列中位于从队首数起的第 $P_i$ 个位置。 * 接下来的 $N-M$ 行中，第 $i$ 行 ($1 \le i \le N-M$) 包含一个整数 $D_{i+M}$。这表示贵族 $(i+M)$ 的舞蹈技巧为 $D_{i+M}$。

向标准输出输出一行，包含一个整数，表示与 JOI 姬配对的贵族的舞蹈技巧可能达到的最大值。

### 样例解释 1 初始状态下，有 $3$ 位贵族的队列位置已经确定。 :::align{center}  括号内的数字表示舞蹈技巧。左端是队列的头部。 ::: 例如，考虑按以下顺序排列：贵族 5，贵族 1，贵族 4，贵族 6，贵族 2，贵族 3，贵族 7。 :::align{center}  所有贵族排列完毕后的配置 ::: 在这种情况下，队列的变化如下： * 队列最前面的三位贵族（贵族 5，贵族 1，贵族 4）中，舞蹈技巧最大的贵族 4 和舞蹈技巧最小的贵族 5 组成一对，剩下的贵族 1 移动到队尾。 * 接着，队列最前面的三位贵族（贵族 6，贵族 2，贵族 3）中，舞蹈技巧最大的有贵族 6 和贵族 3 两人，其中编号较小的是贵族 3。同时，这三位贵族中舞蹈技巧最小的是贵族 2。贵族 3 和贵族 2 组成一对，剩下的贵族 6 移动到队尾。 * 接着，队列最前面的三位贵族（贵族 7，贵族 1，贵族 6）中，舞蹈技巧最大的贵族 7 和舞蹈技巧最小的贵族 1 组成一对，剩下的贵族 6 移动到队尾。 * 最终剩下贵族 6，他将与 JOI 姬组成一对。 贵族 6 的舞蹈技巧是 $8$。这个值是能与 JOI 姬配对的贵族的舞蹈技巧可能达到的最大值。 :::align{center}  队列变化的过程 ::: ### 样例解释 2 无论以何种顺序排列，最终与 JOI 姬配对的都是贵族 2。 ### 数据范围 所有输入数据满足以下条件： * $3 \le N \le 99999$。 * $N$ 是奇数。 * $1 \le M \le N-2$。 * $1 \le D_i \le 1000000000$ ($1 \le i \le N$)。 * $1 \le P_i \le N$ ($1 \le i \le M$)。 * $P_i \ne P_j$ ($1 \le i < j \le M$)。（即初始位置互不相同） ### 子任务 #### 子任务 1 [8 分] * 满足 $N \le 9$。 #### 子任务 2 [16 分] * 满足 $N \le 19$。 #### 子任务 3 [44 分] * 满足 $N \le 1999$。 #### 子任务 4 [32 分] 没有额外限制。 翻译由 DeepSeek V3.2 完成