#「JOI 2014/2015 决赛」舞会

题目描述

译自 JOI 2014/2015 决赛 T4「舞踏会」

IOI 王国为了庆祝 JOI 公主的生日，举行了舞会。 预定有 $N$ 位贵族要参加舞会。 $N$ 是奇数。将贵族们从 $1$ 到 $N$ 编号。每个贵族有一个由整数表示的舞蹈熟练度 。贵族 $i(1 \leq i \leq N)$ 舞蹈熟练度为 $D_i$。 舞会中，含 JOI 公主在内的 $N+1$ 人两两一组跳舞。 IOI 王国遵循老手帮新手的传统，按以下方法决定跳舞的分组。

• 开始时， $N$ 个贵族排成一列。
• 直到队列中只剩下一个贵族为止，不断进行以下操作。
• 调查最前面 $3$ 个贵族的舞蹈熟练度。
• 这 $3$ 个人中舞蹈熟练度最大的贵族称为 $A$ 。如果存在多个人，从中选出序号最小的称为 $A$ 。
• 这 $3$ 个人中舞蹈熟练度最小的贵族称为 $B$ 。如果存在多个人，从中选出序号最大的称为 $B$ 。
• $A$ 和 $B$ 离开队列并组成一组。
• 这三人中没有被选择的一个人移动到队列最后。
• 最后剩下的一个人和 JOI 公主一组。

从第 $1$ 个贵族到第 $M(1 \leq M \leq N-2)$ 个贵族的 $M$ 个贵族已经决定了自己开始时排在队列的第几个。剩下的 $N-M$ 个贵族的排列方式可以由国王自由决定。

因为 JOI 公主才刚开始学跳舞，国王想知道和 JOI 公主组队的贵族的舞蹈熟练度的最大值。

任务

给出每个贵族的舞蹈熟练度，和 $M$ 个贵族开始时在队列中的位置。请编写程序求出和 JOI 公主一组的贵族的舞蹈熟练度的最大值。 第一行为两个以空格分开的整数 $N,M$ 。分别表示舞会有 $N$ 个贵族参加，已经决定排列位置的贵族有 $M$ 人。
接下来 $M$ 行中，第 $i$ 行 $(1\leq i \leq M)$ 为两个以空格分开的整数 $D_i,P_i$ 。分别表示第 $i$ 个贵族的舞蹈熟练度为 $D_i$。贵族 $i$ 开始时排在队列的第 $P_i$ 位。
接下来 $N-M$ 行中，第 $i$ 行 $(1\leq i \leq N-M)$ 为一个整数 $D_{i+M}$。表示贵族 $(i+M)$ 的舞蹈的熟练度为 $D_{i+M}$。 输出一行：表示和 JOI 公主组队的贵族的舞蹈熟练度的最大值。

输入样例 1

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

输出样例 1

8

样例解释 1

开始时有 $3$ 个人的位置是确定的。

括号内的数字表示舞蹈的熟练度，左端是队列的开始。

举例来说，考虑从队首开始的贵族的序号分别为$5,1,4,6,2,3,7$时：

这时队列会依次发生以下变化：

• 队列最前面的 $3$ 个贵族（贵族 $5$ ，贵族 $1$ ，贵族 $4$ ） 中，舞蹈熟练度最大的人（贵族 $4$ ）和舞蹈熟练度最小的人（贵族 $5$ ）组队，剩下的贵族 $1$ 移动到队尾。
• 接下来，队列最前面的 $3$ 个贵族（贵族 $6$ ，贵族 $2$ ，贵族 $3$ ） 中，舞蹈熟练度最大的人有两个：贵族 $6$ 和贵族 $3$ ，其中序号比较小的为贵族 $3$ 。而前 $3$ 人中舞蹈熟练度最小的人为贵族 $2$ ，所以贵族 $3$ 和贵族 $2$ 组队。剩下的贵族 $6$ 移动到队尾。
• 接下来，队列最前面的 $3$ 个贵族（贵族 $7$ ，贵族 $1$ ，贵族 $6$ ） 中，舞蹈熟练度最大的人（贵族 $7$ ）和舞蹈熟练度最小的人（贵族 $1$ ）组队，剩下的贵族 $6$ 移动到队尾。
• 最后剩下的是贵族 $6$ ，他将和 JOI 公主一组。

贵族 $6$ 的舞蹈熟练度为 $8$ ，这就是和 JOI 公主一组的贵族舞蹈熟练度最大值。

输入样例 2

3 1
5 3
5
5

输出样例 2

5

输入样例 3

7 2
32 4
27 6
37
41
41
30
27

输出样例 3

37

对于 $8\%$ 的数据：

• $N \leq 9$

对于另 $16\%$ 的数据：

• $N \leq 19$

对于另 $44\%$ 的数据：

• $N \leq 1999$

对于 $100\%$ 的数据，

• $3 \leq N \le 99999$
• $N$ 为奇数
• $1 \leq D_i \leq 10^9 (1 \leq i \leq N)$
• $1 \leq P_i \leq N (1 \leq i \leq M)$
• $P_i \not = P_j (1 \leq i\lt j \leq M)$

感谢 Planet6174 提供的翻译