小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得分的最大值。

【样例说明】

最高得分的评分排列： 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).

2025年11月婺城区第三届青少年信息素养大赛初中组试题

市赛