2727 「JOI 2015 Final」舞会

译自 JOI 2015 Final 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 公主组队的贵族的舞蹈熟练度的最大值。

开始时有 $ 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 公主一组的贵族舞蹈熟练度最大值。

对于 $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)$