LCC/Moose '20 Contest 4 S4 - Alan and Partner

View as PDF

Submit solution

Points: 15 (partial)
Time limit: 2.0s
Memory limit: 64M

Problem type

As we all know, Alan is the coolest, and thus everyone wants to date him. This makes his decision in who to make his partner difficult. Thus, Alan has decided on an algorithm he will use to determine his partner. There are N possible partners for Alan, each with an attractiveness value a_i (of course Alan is not shallow, this includes personality too). He will line them up, and repeat the following process until one person remains:

  • Consider the first 3 people in the line:
  • Since Alan has standards, he will not date the person with the minimum a_i of the three.
  • Since Alan is humble, he will not date the person with the maximum a_i of the three.
  • These two people are removed from the line, and the remaining person of the three is sent to the back of the line.
  • Ties are broken arbitrarily by Alan's friend Peter, since Alan is indecisive.

M of Alan's prospective partners are so excited for the opportunity to date Alan that they have arrived early and chosen a spot in the line. The other N-M however have been stopped by Peter, who has a plan. Peter wants the best for Alan, so he will place the remaining N-M people in the line such that Alan's date ends up with the maximum possible a_i. If Peter places the remaining people optimally, what will be the a_i of Alan's partner?

Input Specification

The first line will contain two integers N\ (1 \leq N \leq 10^5), N is odd, and M\ (1 \leq M \leq N-2).

The next M lines will contain two integers a_i\ (1 \leq a_i\leq 10^9) and p_i\ (1 \leq p_i \leq N), representing the attractiveness and the position of the i^\text{th} person.

The next N-M lines will contain the integer a_i\ (1 \leq a_i \leq 10^9), representing the attractiveness of one of the people stopped by Peter.

Output Specification

On one line, you are to output the attractiveness of Alan's partner, given Peter places the remaining people optimally.


Subtask 1 (5%)

N \leq 10

Subtask 2 (5%)

N \leq 20

Subtask 3 (30%)

N \leq 2\cdot 10^3

Subtask 4 (60%)

No further constraints.

Sample Input

7 3
5 2
5 5
8 6

Sample Output



There are no comments at the moment.