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