说明

在 IOI 王国，为了庆祝公主 JOI 姬的生日，将举办一场舞会。

舞会预计有 $N$ 位贵族参加。$N$ 是奇数。贵族们被编号为 $1$ 到 $N$。每位贵族都有一个被称为“舞蹈技巧”的整数值，贵族 $i$ ($1 \le i \le N$) 的舞蹈技巧为 $D_i$。

舞会上，包括 JOI 姬在内的 $N+1$ 人将两两配对跳舞。在 IOI 王国，为了能让资深者辅助初学者，传统上按以下方法决定舞蹈配对：

• 首先，$N$ 位贵族排成一列。
• 重复以下操作，直到队列中只剩下一人：
  • 检查队列最前面三位贵族的舞蹈技巧。
  • 在这三位贵族中，将舞蹈技巧最大的贵族记为 A。如果有多个舞蹈技巧最大的贵族，则取其中编号最小的贵族作为 A。
  • 在这三位贵族中，将舞蹈技巧最小的贵族记为 B。如果有多个舞蹈技巧最小的贵族，则取其中编号最大的贵族作为 B。
  • A 和 B 离开队列，组成一对。
  • 剩下的一位贵族移动到队列的末尾。
• 最后剩下的那一位贵族将与 JOI 姬组成一对。

对于贵族 1 到贵族 $M$ ($1 \le M \le N-2$) 这 $M$ 位贵族，他们在初始队列中的位置已经确定。剩下的 $N-M$ 位贵族的排列顺序可以由国王自由决定。

JOI 姬刚开始学习跳舞，因此国王希望与 JOI 姬配对的贵族的舞蹈技巧尽可能大。请求出与 JOI 姬配对的贵族的舞蹈技巧可能达到的最大值。

任务

给定每位贵族的舞蹈技巧以及 $M$ 位贵族在初始队列中的位置，请编写一个程序，计算与 JOI 姬配对的贵族的舞蹈技巧可能达到的最大值。

输入格式

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

• 第一行包含两个以空格分隔的整数 $N, M$。这表示舞会有 $N$ 位贵族参加，且队列中已有 $M$ 位贵族的位置被确定。
• 接下来的 $M$ 行中，第 $i$ 行 ($1 \le i \le M$) 包含两个以空格分隔的整数 $D_i, P_i$。这表示贵族 $i$ 的舞蹈技巧为 $D_i$，且他在初始队列中位于从队首数起的第 $P_i$ 个位置。
• 接下来的 $N-M$ 行中，第 $i$ 行 ($1 \le i \le 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

提示

样例解释 1

初始状态下，有 $3$ 位贵族的队列位置已经确定。

:::align{center}

括号内的数字表示舞蹈技巧。左端是队列的头部。 :::

例如，考虑按以下顺序排列：贵族 5，贵族 1，贵族 4，贵族 6，贵族 2，贵族 3，贵族 7。

:::align{center}

所有贵族排列完毕后的配置 :::

在这种情况下，队列的变化如下：

• 队列最前面的三位贵族（贵族 5，贵族 1，贵族 4）中，舞蹈技巧最大的贵族 4 和舞蹈技巧最小的贵族 5 组成一对，剩下的贵族 1 移动到队尾。
• 接着，队列最前面的三位贵族（贵族 6，贵族 2，贵族 3）中，舞蹈技巧最大的有贵族 6 和贵族 3 两人，其中编号较小的是贵族 3。同时，这三位贵族中舞蹈技巧最小的是贵族 2。贵族 3 和贵族 2 组成一对，剩下的贵族 6 移动到队尾。
• 接着，队列最前面的三位贵族（贵族 7，贵族 1，贵族 6）中，舞蹈技巧最大的贵族 7 和舞蹈技巧最小的贵族 1 组成一对，剩下的贵族 6 移动到队尾。
• 最终剩下贵族 6，他将与 JOI 姬组成一对。

贵族 6 的舞蹈技巧是 $8$。这个值是能与 JOI 姬配对的贵族的舞蹈技巧可能达到的最大值。

:::align{center}

队列变化的过程 :::

样例解释 2

无论以何种顺序排列，最终与 JOI 姬配对的都是贵族 2。

数据范围

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

• $3 \le N \le 99999$。
• $N$ 是奇数。
• $1 \le M \le N-2$。
• $1 \le D_i \le 1000000000$ ($1 \le i \le N$)。
• $1 \le P_i \le N$ ($1 \le i \le M$)。
• $P_i \ne P_j$ ($1 \le i < j \le M$)。（即初始位置互不相同）

子任务

子任务 1 [8 分]

• 满足 $N \le 9$。

子任务 2 [16 分]

• 满足 $N \le 19$。

子任务 3 [44 分]

• 满足 $N \le 1999$。

子任务 4 [32 分]

没有额外限制。

翻译由 DeepSeek V3.2 完成