题目描述

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

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

8

3 1
5 3
5
5

5

7 2
32 4
27 6
37
41
41
30
27

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