题目描述

译自 JOI 2015 Final T4「舞踏会」

IOI 王国为了庆祝 JOI 公主的生日，举行了舞会。预定有 $N$ 位贵族要参加舞会。$N$ 是奇数。将贵族们从 $1$ 到 $N$ 编号。每个贵族有一个由整数表示的舞蹈熟练度。贵族 $i$ $(1 \leq i \leq N)$ 舞蹈熟练度为 $D_i$。

舞会中，含 JOI 公主在内的 $N+1$ 人两两一组跳舞。IOI 王国遵循老手帮新手的传统，按以下方法决定跳舞的分组。

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

输出

8

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

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

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

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

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

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

---

样例 2

输入

3 1
5 3
5
5

输出

5

---

样例 3

输入

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 \leq 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 \neq P_j$ $(1 \leq i < j \leq M)$