P15819 [JOI 2015 Final] Prom / Ball

In the IOI Kingdom, a ball will be held to celebrate the birthday of Princess JOI. There will be $N$ nobles attending the ball. $N$ is odd. The nobles are numbered from $1$ to $N$. Each noble has an integer value called “dance skill”. The dance skill of noble $i$ ($1 \le i \le N$) is $D_i$. At the ball, the $N + 1$ people (including Princess JOI) will be paired up to dance. In the IOI Kingdom, in order for experienced people to help beginners, dance pairs are traditionally decided in the following way: * First, the $N$ nobles stand in a single line (a queue). * Repeat the following operation until only one person remains in the queue: * Check the dance skills of the first three nobles in the queue. * Among these three nobles, let A be the noble with the **largest** dance skill. If there are multiple nobles with the largest dance skill, choose the one with the **smallest index** as A. * Among these three nobles, let B be the noble with the **smallest** dance skill. If there are multiple nobles with the smallest dance skill, choose the one with the **largest index** as B. * A and B leave the queue and form a pair. * The remaining noble moves to the end of the queue. * The last remaining noble will form a pair with Princess JOI. For nobles $1$ to $M$ ($1 \le M \le N-2$), the positions of these $M$ nobles in the initial queue are already fixed. The order of the remaining $N-M$ nobles can be decided freely by the king. Princess JOI has just started learning to dance, so the king wants the dance skill of the noble who pairs with Princess JOI to be as large as possible. Find the maximum possible value of the dance skill of the noble who pairs with Princess JOI. ### Task Given the dance skills of all nobles and the positions of the $M$ nobles in the initial queue, write a program to compute the maximum possible dance skill of the noble who can be paired with Princess JOI.

Read the following from standard input. * The first line contains two integers $N, M$ separated by spaces. This means there are $N$ nobles attending the ball, and the positions of $M$ nobles in the queue are already fixed. * In the next $M$ lines, the $i$-th line ($1 \le i \le M$) contains two integers $D_i, P_i$ separated by spaces. This means the dance skill of noble $i$ is $D_i$, and in the initial queue he is at position $P_i$ counted from the front. * In the next $N-M$ lines, the $i$-th line ($1 \le i \le N-M$) contains one integer $D_{i+M}$. This means the dance skill of noble $(i+M)$ is $D_{i+M}$.

Output one line to standard output containing one integer, which is the maximum possible dance skill of the noble who can be paired with Princess JOI.

### Sample Explanation 1 Initially, the queue positions of $3$ nobles are already fixed. :::align{center}  The numbers in parentheses indicate dance skills. The left end is the head of the queue. ::: For example, consider arranging them in the following order: noble 5, noble 1, noble 4, noble 6, noble 2, noble 3, noble 7. :::align{center}  The configuration after all nobles are arranged. ::: In this case, the queue changes as follows: * Among the first three nobles in the queue (noble 5, noble 1, noble 4), the noble with the largest dance skill, noble 4, and the noble with the smallest dance skill, noble 5, form a pair. The remaining noble 1 moves to the end of the queue. * Next, among the first three nobles in the queue (noble 6, noble 2, noble 3), the nobles with the largest dance skill are noble 6 and noble 3; the one with the smaller index is noble 3. Also, among these three nobles the one with the smallest dance skill is noble 2. Noble 3 and noble 2 form a pair, and the remaining noble 6 moves to the end of the queue. * Next, among the first three nobles in the queue (noble 7, noble 1, noble 6), the noble with the largest dance skill, noble 7, and the noble with the smallest dance skill, noble 1, form a pair. The remaining noble 6 moves to the end of the queue. * Finally, noble 6 remains, and he will form a pair with Princess JOI. The dance skill of noble 6 is $8$. This value is the maximum possible dance skill of the noble who can be paired with Princess JOI. :::align{center}  The process of the queue changes. ::: ### Sample Explanation 2 No matter in which order they are arranged, the noble who is finally paired with Princess JOI is noble 2. ### Constraints All input data satisfy the following: * $3 \le N \le 99999$。 * $N$ is odd. * $1 \le M \le N-2$。 * $1 \le D_i \le 1000000000$ ($1 \le i \le N$)。 * $1 \le P_i \le N$ ($1 \le i \le M$)。 * $P_i \ne P_j$ ($1 \le i < j \le M$). (That is, the initial positions are all different.) ### Subtasks #### Subtask 1 [8 points] * Satisfies $N \le 9$. #### Subtask 2 [16 points] * Satisfies $N \le 19$. #### Subtask 3 [44 points] * Satisfies $N \le 1999$. #### Subtask 4 [32 points] No additional constraints. The translation was done by DeepSeek V3.2. Translated by ChatGPT 5