IOI 王国中，为了庆祝王女 JOI 姬的生日，将举行一场舞会。

计划中将有 N 位贵族参加舞会，N 是一个奇数。每个贵族都有一个编号从 1 到 N，并且每个贵族都有一个整数表示他们的舞技，贵族 i（1 ≤ i ≤ N）的舞技值为 Di。

在舞会中，JOI 姬将和其他 N + 1 个人分成两人一组跳舞。为了使初级者可以得到资深者的帮助，IOI 王国通常按照以下方法决定舞伴：

• 首先，N 个贵族站成一列。
• 反复进行以下步骤，直到只剩下一个贵族：
  • 检查列中前三个贵族的舞技值。
  • 在这三个贵族中，选择舞技值最高的贵族作为 A。如果有多位舞技值相同的贵族，选择编号最小的贵族作为 A。
  • 在这三个贵族中，选择舞技值最低的贵族作为 B。如果有多位舞技值相同的贵族，选择编号最大的贵族作为 B。
  • A 和 B 形成一对，并离开列。
  • 剩下一个人移动到列的末尾。
• 最后剩下的一个贵族将和 JOI 姬成为舞伴。贵族 1 到贵族 M（1 ≤ M ≤ N - 2）已经在初始状态下决定了他们在列中的位置，剩下的 N - M 个贵族的位置可以由国王随意决定。

由于 JOI 姬刚刚开始学习舞蹈，国王希望最大化与 JOI 姬成为舞伴的贵族的舞技值。请计算与 JOI 姬成为舞伴的贵族舞技值可能的最大值。

问题

在给定每个贵族的舞技值以及 M 个贵族的初始位置后，编写一个程序来计算与 JOI 姬成为舞伴的贵族舞技值的最大可能值。

输入

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

• 第 1 行包含两个整数 N 和 M，用空格分隔。表示有 N 位贵族参加舞会，并且已经确定了 M 位贵族在列中的位置。
• 接下来的 M 行中的第 i 行（1 ≤ i ≤ M）包含两个整数 Di 和 Pi，用空格分隔。表示第 i 位贵族的舞技值为 Di，且该贵族在初始状态下在列中的位置为第 Pi 个。
• 接下来的 N - M 行中的第 i 行（1 ≤ i ≤ N - M）包含一个整数 Di+M。表示第 i + M 位贵族的舞技值为 Di+M。

输出

将计算结果输出到标准输出，表示与 JOI 姬成为舞伴的贵族舞技值的最大可能值，以一个整数的形式输出。

示例

输入示例 1

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

输出示例 1

8

在初始状态下，已经确定了 3 位贵族的位置。

括号内的数字表示舞技值，最左侧是列的开头。

例如，考虑贵族依次排列为 5，1，4，6，2，3，7 的情况。

列中所有贵族都排好序后的状态

在这种情况下，列发生以下变化：

• 计算列中前三个贵族的舞技值（5，1，4）。其中，舞技值最高的贵族是贵族 4，舞技值最低的贵族是贵族 5，所以贵族 4 和贵族 5 成为一对，剩余的贵族 1 移动到列的末尾。
• 接下来，计算列中前三个贵族的舞技值（6，2，3）。其中，舞技值最高的贵族是贵族 6 和贵族 3（两人舞技值相同）中编号较小的贵族，此处为贵族 3。列中前三个贵族中舞技值最低的贵族是