A71956. 选秀得分
题目描述
小Z最近参加一个选秀比赛，有 N 个评委参加了这次评分， N 是奇数。评委编号为 1 到 N 。每位评委给小Z打的分数是一个整数，评委 i ( 1 \leq i \leq N ) 的打分为 D_i 。
这次采用了一种创新的方法计算最后得分，计算规则是：
- 最初 N 位评委排成一排，检查队伍排头的3位评委的评分，去掉一个最高分和一个最低分，剩下的一个评委移动到队伍最后；
- 反复执行以上操作，直到队伍中的评委只剩一位。
那么这个评委的打分就是小Z的最后得分。
由于有的评委年纪比较大了，不记得自己的位置了，现在有 M ( 1 \leq M \leq N - 2 ) 个评委很快找到了自己的位置，剩下的 N - M 人找不到位置了，需要给他们重新安排位置。
由于小Z希望自己的得分尽可能高，请你帮忙计算出小Z最后得分可能的最大值。
输入格式
第一行为整数 N 和 M ，用空格分隔。表示有 N 位评委，其中 M 人的初始排列位置已经确定。
接下来 M 行中第 i ( 1 \leq i \leq M ) 行为两个整数 D_i 和 P_i ，用空格分隔。表示第 i 位评委的评分为 D_i ，初始排列位置为队伍排头开始的第 P_i 位。
接下来 N - M 行整数，表示 N - M 个不清楚位置的评委的评分。
输出格式
输出一行，为一个整数，表示小Z得分的最大值。
输入输出样例
7 3 5 2 5 5 8 6 6 2 8 9
8
说明/提示
【样例说明】
最高得分的评分排列： 2, 5, 6, 8, 5, 8, 9
【数据范围】
10\% 的数据：所有 D_i 都相等。
40\% 的数据： 3 \leq N \leq 5000 , D_i \leq 5000 。
100\% 的数据：
3 \leq N \leq 99999,
1 \leq M \leq N - 2,
1 \leq D_i \leq 10^9 \quad (1 \leq i \leq N),
1 \leq P_i \leq N \quad (1 \leq i \leq M),
P_i \neq P_j \quad (1 \leq i < j \leq M).