Coding Contest

Time limit1sMemory limit256 MB

Summary

Place coders in the free starting slots so the queue contest that pairs the strongest and weakest of each front triple leaves the strongest possible survivor.

Level: Medium7 of 10
Topics: Binary search, Simulation, Greedy
Solved: No attempts yet

Problem

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.

Input

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.

Output

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

Constraints

$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$ )

Examples3

Example 1
Input
```
7 3
5 2
5 5
8 6
6
2
8
9
```
Expected output
```
8
```
Example 2
Input
```
3 1
5 3
5
5
```
Expected output
```
5
```
Example 3
Input
```
7 2
32 4
27 6
37
41
41
30
27
```
Expected output
```
37
```