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

$N$ nobles are scheduled to attend the ball. $N$ is an odd number. The nobles are numbered from $1$ to $N$. Each noble has an integer value representing their dancing skill, and the dancing skill of noble $i$ ($1 \le i \le N$) is $D_i$.

At the ball, $N+1$ people, including Princess JOI, will form pairs to dance. In the Kingdom of IOI, to allow advanced dancers to assist beginners, the dancing pairs are traditionally determined as follows:

• Initially, the $N$ nobles line up in a row.
• The following operation is repeated until only one noble remains in the row:
  • Examine the dancing skills of the first 3 nobles in the row.
  • Let $A$ be the noble with the highest dancing skill among these 3. If there is a tie, let $A$ be the noble with the smallest ID among those with the highest dancing skill.
  • Let $B$ be the noble with the lowest dancing skill among these 3. If there is a tie, let $B$ be the noble with the largest ID among those with the lowest dancing skill.
  • $A$ and $B$ leave the row and form a pair.
  • The remaining 1 noble moves to the end of the row.
• The final remaining noble forms a pair with Princess JOI.

For $M$ nobles from noble $1$ to noble $M$ ($1 \le M \le N-2$), their positions in the initial row are already determined. The King can freely decide the arrangement of the remaining $N-M$ nobles.

Since Princess JOI has just learned to dance, the King wants to maximize the dancing skill of the noble who forms a pair with Princess JOI. Find the maximum possible dancing skill of the noble who forms a pair with Princess JOI.

Input

Read the following data from standard input:

• The first line contains two integers $N$ and $M$, separated by a space. This indicates that $N$ nobles are participating in the ball, and the positions of $M$ nobles in the row are already determined.
• The $i$-th line of the following $M$ lines ($1 \le i \le M$) contains two integers $D_i$ and $P_i$, separated by a space. This indicates that the dancing skill of noble $i$ is $D_i$, and noble $i$ is initially at the $P_i$-th position from the front of the row.
• The $i$-th line of the following $N-M$ lines ($1 \le i \le N-M$) contains an integer $D_{i+M}$. This indicates that the dancing skill of noble $(i+M)$ is $D_{i+M}$.

Output

Output the maximum possible dancing skill of the noble who forms a pair with Princess JOI as an integer on a single line.

Constraints

All input data satisfies the following conditions:

• $3 \le N \le 99\,999$.
• $N$ is an odd number.
• $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$).

Subtasks

Subtask 1 [8 points]

• $N \le 9$ is satisfied.

Subtask 2 [16 points]

• $N \le 19$ is satisfied.

Subtask 3 [44 points]

• $N \le 1\,999$ is satisfied.

Subtask 4 [32 points]

• There are no additional constraints.

Examples

Input 1

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

Output 1

8

Input 2

3 1
5 3
5
5

Output 2

5

Input 3

7 2
32 4
27 6
37
41
41
30
27

Output 3

37