在 IOI 王国，为了庆祝公主 JOI 的生日，将举办一场舞会。 舞会将有 $N$ 名贵族参加。$N$ 是一个奇数。贵族被编号为 1 到 $N$。每位贵族都有一个被称为“舞技”的整数值，贵族 $i$ ($1 \le i \le N$) 的舞技为 $D_i$。

在舞会上，包括 JOI 公主在内的 $N+1$ 人将两两配对跳舞。在 IOI 王国，为了让高级别者能够辅助初级别者，传统上采用以下方法来决定舞伴：

• 首先，将 $N$ 名贵族排成一列。
• 在队列中只剩下一名贵族之前，重复执行以下操作：
  • 检查队列最前端的 3 名贵族。
  • 在这 3 名贵族中，将舞技最高者设为 $A$。若有多人舞技最高，则将其中编号最小者设为 $A$。
  • 在这 3 名贵族中，将舞技最低者设为 $B$。若有多人舞技最低，则将其中编号最大者设为 $B$。
  • $A$ 和 $B$ 离开队列并成为舞伴。
  • 剩下的 1 人移动到队列的最后方。
• 最终剩下的一人将与 JOI 公主成为舞伴。

对于贵族 1 到贵族 $M$ ($1 \le M \le N-2$) 这 $M$ 名贵族，其在初始状态下队列中的位置已经确定。其余 $N-M$ 名贵族的排列方式由国王自由决定。

由于 JOI 公主刚开始学习跳舞，国王希望与 JOI 公主成为舞伴的贵族的舞技尽可能高。请计算与 JOI 公主成为舞伴的贵族的舞技可能达到的最大值。

题目描述

给定每位贵族的舞技以及 $M$ 名贵族在初始状态下的位置，编写一个程序，计算与 JOI 公主成为舞伴的贵族的舞技可能达到的最大值。

输入格式

从标准输入读取以下数据：

• 第 1 行包含两个整数 $N, M$，以空格分隔。这表示有 $N$ 名贵族参加舞会，其中有 $M$ 名贵族的位置已经确定。
• 接下来的 $M$ 行中，第 $i$ 行 ($1 \le i \le M$) 包含两个整数 $D_i, P_i$，以空格分隔。这表示贵族 $i$ 的舞技为 $D_i$，且贵族 $i$ 在初始状态下位于队列从前端起的第 $P_i$ 个位置。
• 接下来的 $N-M$ 行中，第 $i$ 行 ($1 \le i \le N-M$) 包含一个整数 $D_{i+M}$。这表示贵族 $(i+M)$ 的舞技为 $D_{i+M}$。

输出格式

将与 JOI 公主成为舞伴的贵族的舞技可能达到的最大值作为一个整数输出到标准输出。

数据范围

所有输入数据满足以下条件：

• $3 \le N \le 99\,999$
• $N$ 是奇数
• $1 \le M \le N-2$
• $1 \le D_i \le 1\,000\,000\,000$ ($1 \le i \le N$)
• $1 \le P_i \le N$ ($1 \le i \le M$)
• $P_i \neq P_j$ ($1 \le i < j \le M$)

子任务

1. (8 分) 满足 $N \le 9$。
2. (16 分) 满足 $N \le 19$。
3. (44 分) 满足 $N \le 1\,999$。
4. (32 分) 无额外限制。

样例

样例输入 1

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

样例输出 1

8

样例输入 2

3 1
5 3
5
5

样例输出 2

5

样例输入 3

7 2
32 4
27 6
37
41
41
30
27

样例输出 3

37