Problem Description

In the Kingdom of IOI, a ball is being held to celebrate the birthday of Princess JOI.

The ball is scheduled to have $N$ nobles attending. $N$ is an odd number. Each noble is assigned a unique number from $1$ to $N$. Each noble also has an integer value called dance skill, where the dance skill of noble $i$ ($1 \leq i \leq N$) is $D_i$.

At the ball, $N + 1$ people including Princess JOI will dance in pairs of two. In the Kingdom of IOI, the tradition is to determine dance pairs in the following way to ensure that an experienced dancer can assist a less experienced one:

• Initially, $N$ nobles line up in a row.
• Until there is only one noble left in the row, repeat the following operations:
• Examine the dance skills of the first three nobles in the row.
• Let $A$ be the noble with the highest dance skill among these three. If there are multiple nobles with the highest dance skill, choose the one with the smallest number.
• Let $B$ be the noble with the lowest dance skill among these three. If there are multiple nobles with the lowest dance skill, choose the one with the largest number.
• $A$ and $B$ exit the row and form a pair.
• The remaining one noble moves to the end of the row.
• The last remaining noble will dance with Princess JOI. For $M$ nobles ($1 \leq M \leq N - 2$), their initial positions in the row are already determined. The king can freely decide the order of the remaining $N - M$ nobles.

Since Princess JOI is new to dancing, the king wants to maximize the dance skill of the noble who will dance with her. Determine the maximum possible dance skill of the noble who will dance with Princess JOI.

Input Format

Read the following data from the standard input:

• The first line contains two integers $N$ and $M$, separated by a space. This indicates that there are $N$ nobles attending the ball and $M$ nobles whose initial positions in the row are already determined.
• The next $M$ lines contain two integers $D_i$ and $P_i$, separated by a space. This indicates that noble $i$ has a dance skill of $D_i$ and will initially stand at the $P_i$-th position from the front of the row.
• The next $N - M$ lines contain one integer $D_{i + M}$. This indicates that noble ($i + M$) has a dance skill of $D_{i + M}$.

Output Format

Output the maximum possible dance skill of the noble who will dance with Princess JOI as a single integer on one line to the standard output.

Sample Input and Output

Sample Input #1

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

Sample Output #1

8

Sample Input #2

3 1
5 3
5
5

Sample Output #2

5

Sample Input #3

7 2
32 4
27 6
37
41
41
30
27

Sample Output #3

37

Notes/Hints

Task

Given the dance skills of each noble and the initial positions of $M$ nobles, write a program to find the maximum possible dance skill of the noble who will dance with Princess JOI.

Constraints

All input data satisfies the following conditions:

• $3 \leq N \leq 99,999$.
• $N$ is an odd number.
• $1 \leq M \leq N - 2$.
• $1 \leq D_i \leq 1,000,000,000$ ($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$).

Subtasks

Subtask 1 [8 points]

• $N \leq 9$.

Subtask 2 [16 points]

• $N \leq 19$.

Subtask 3 [44 points]

• $N \leq 1,999$.

Subtask 4 [32 points]

No additional constraints.

Sample Explanation 1

In the initial state, the positions of $3$ nobles are already determined. For example, if the nobles line up in the order of noble $5$, noble $1$, noble $4$, noble $6$, noble $2$, noble $3$, and noble $7$ from the front, the following changes occur in the row:

• The first three nobles (noble $5$, noble $1$, noble $4$) form a pair with noble $4$ (highest dance skill) and noble $5$ (lowest dance skill), and noble $1$ moves to the end.
• The next three nobles (noble $6$, noble $2$, noble $3$) form a pair with noble $3$ (highest dance skill, smallest number) and noble $2$ (lowest dance skill), and noble $6$ moves to the end.
• The next three nobles (noble $7$, noble $1$, noble $6$) form a pair with noble $7$ (highest dance skill) and noble $1$ (lowest dance skill), and noble $6$ moves to the end.
• Finally, noble $6$ remains and dances with Princess JOI. The dance skill of noble $6$ is $8$, which is the maximum possible value.

Sample Explanation 2

Regardless of the order, noble $2$ will dance with Princess JOI.

见题面 Input 部分

见题面 Output 部分