TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P5959
  • 题目
  • P5959比赛评分
    限制 : 时间限制 : - MS   空间限制 : - KB
    评测说明 : 1s,128m
    问题描述

    Lj​最近参加一个选秀比赛,有N个评委参加了这次评分,N是奇数。
    评委编号为1到N。每位评委给Lj​的分数是一个整数,评委$i(1 \leq i \leq N)$的打分为$D_i$。
    这次采用了一种创新的方法计算最后得分,计算规则是:
      最初N位评委排成一排,检查队伍排头的3位评委的评分,去掉一个最高分和一个最低分,剩下的一个评委移动到队伍最后,反复执行以上操作,直到队伍中的评委只剩一位,那么这个评委的打分就是Lj的最后得分
    由于有的评委年纪比较大了,不记得自己的位置了,现在有$M(1 \leq M \leq N - 2)$个评委很快找到了自己的位置,剩下的$N-M$人找不到位置了,需要给他们重新安排位置。
    由于Lj希望自己的得分尽可能高。请你帮忙计算出LJ最后得分可能的最大值。

    输入格式

    第一行为整数N和M,用空格分隔。表示有N位评委,其中M人的初始排列位置已经确定。

    接下来M行中第i行$(1 \leq i \leq M)$为两个整数$D_i$和$P_i$,用空格分隔。

    表示第i位评委的评分为Di,初始排列位置为队伍排头开始的第Pi位。 接下来$N-M$行中第i行为整数$D_{i+M}$,表示评委(i+M)的评分为$D_{i+M}$。 3 ≦ N ≦ 99 999,
    1 ≦ M ≦ N - 2,
    $1 ≦ D_i ≦ 10^9 (1 ≦ i ≦ N)$,
    1 ≦ Pi ≦ N (1 ≦ i ≦ M),
    Pi != Pj (1 ≦ i < j ≦ M)。

    输出格式

    输出一行,为1个整数,表示LJ得分的最大值。

    样例输入 1

    7 3 
    5 2 
    5 5 
    8 6 



    9

    样例输出 1

    8

    样例输入 2

    9 2
    700064284 3
    805336870 6
    503971033
    711342034
    929082548
    143239206
    42519425
    58389173
    572744325

    样例输出 2

    700064284

    提示

    样例1说明: //最高得分的评分排列:2, 5, 6, 8, 5, 8, 9


    来源  bzoj 4985