Coding Contest

The club is holding a coding contest for Sujin's birthday.

N coders numbered 1 through N enter the contest, and coder $i$ has a skill value $D_i$. N is odd.

The contest is played in teams of two, so the N + 1 people, Sujin included, split into pairs. The organizers keep the teams balanced by forming them this way.

• Line up the N contestants in a single row.
• Repeat the following until one contestant is left in the row.
  • Look at the skills of the three contestants at the front of the row.
  • Among the three, take the one with the highest skill. If several of them share the highest skill, take the one with the smallest number.
  • Among the three, take the one with the lowest skill. If several of them share the lowest skill, take the one with the largest number.
  • The two contestants taken above form a team and leave the row.
  • Send the remaining contestant to the back of the row.
• The one contestant left at the end teams up with Sujin.

The coders numbered M or below already have a fixed starting position in the row. Sujin can place the remaining N - M coders in the empty positions in any order she likes, and she wants to team up with a coder whose skill is as high as possible. Write a program that computes the largest skill a coder teamed up with Sujin can have.

The first line contains the number of coders N and the number of coders whose starting position is fixed, M.

Each of the next M lines contains the coding skill $D_i$ and the starting position $P_i$ of coder $i$ ($1 \le i \le M$).

Each of the next N - M lines contains the coding skill $D_i$ of coder $i$ ($M + 1 \le i \le N$), one per line.

Print on the first line the largest coding skill a coder teamed up with Sujin can have.

• $3 \le N \le 99999$, and N is odd.
• $1 \le M \le N - 2$
• $1 \le D_i \le 10^9$ ($1 \le i \le N$)
• $1 \le P_i \le N$ ($1 \le i \le M$)
• $P_i \ne P_j$ when $i < j$ ($1 \le i < j \le M$)