#2727. 「JOI 2015 Final」舞会

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: hy1004

题目描述

译自 JOI 2015 Final T4「舞踏会

IOI 王国为了庆祝 JOI 公主的生日,举行了舞会。 预定有 N 位贵族要参加舞会。 N 是奇数。将贵族们从 1 N 编号。每个贵族有一个由整数表示的舞蹈熟练度 。贵族 i(1 \leq i \leq N) 舞蹈熟练度为 D_i 。 舞会中,含 JOI 公主在内的 N+1 人两两一组跳舞。 IOI 王国遵循老手帮新手的传统,按以下方法决定跳舞的分组。

  • 开始时, N 个贵族排成一列。
  • 直到队列中只剩下一个贵族为止,不断进行以下操作。
  • 调查最前面 3 个贵族的舞蹈熟练度。
  • 3 个人中舞蹈熟练度最大的贵族称为 A 。如果存在多个人,从中选出序号最小的称为 A
  • 3 个人中舞蹈熟练度最小的贵族称为 B 。如果存在多个人,从中选出序号最大的称为 B
  • A B 离开队列并组成一组。
  • 这三人中没有被选择的一个人移动到队列最后。
  • 最后剩下的一个人和 JOI 公主一组。

从第 1 个贵族到第 M(1 \leq M \leq N-2) 个贵族的 M 个贵族已经决定了自己开始时排在队列的第几个。剩下的 N-M 个贵族的排列方式可以由国王自由决定。

因为 JOI 公主才刚开始学跳舞,国王想知道和 JOI 公主组队的贵族的舞蹈熟练度的最大值。

任务

给出每个贵族的舞蹈熟练度,和 M 个贵族开始时在队列中的位置。请编写程序求出和 JOI 公主一组的贵族的舞蹈熟练度的最大值。

输入格式

第一行为两个以空格分开的整数 N,M 。分别表示舞会有 N 个贵族参加,已经决定排列位置的贵族有 M 人。
接下来 M 行中,第 i (1\leq i \leq M) 为两个以空格分开的整数 D_i,P_i 。分别表示第 i 个贵族的舞蹈熟练度为 D_i 。贵族 i 开始时排在队列的第 P_i 位。
接下来 N-M 行中,第 i (1\leq i \leq N-M) 为一个整数 D_{i+M} 。表示贵族 (i+M) 的舞蹈的熟练度为 D_{i+M}

输出格式

输出一行:表示和 JOI 公主组队的贵族的舞蹈熟练度的最大值。

样例

输入样例 1

7 3
5 2
5 5
8 6
6
2
8
9

输出样例 1

8

样例解释 1

开始时有 3 个人的位置是确定的。

64f21fcfcd875ef5162872c7ed1e5bdf.png

括号内的数字表示舞蹈的熟练度,左端是队列的开始。

举例来说,考虑从队首开始的贵族的序号分别为 5,1,4,6,2,3,7 时:

23e8501749ededa25.png

这时队列会依次发生以下变化:

  • 队列最前面的 3 个贵族(贵族 5 ,贵族 1 ,贵族 4 ) 中,舞蹈熟练度最大的人(贵族 4 )和舞蹈熟练度最小的人(贵族 5 )组队,剩下的贵族 1 移动到队尾。
  • 接下来,队列最前面的 3 个贵族(贵族 6 ,贵族 2 ,贵族 3 ) 中,舞蹈熟练度最大的人有两个:贵族 6 和贵族 3 ,其中序号比较小的为贵族 3 。而前 3 人中舞蹈熟练度最小的人为贵族 2 ,所以贵族 3 和贵族 2 组队。剩下的贵族 6 移动到队尾。
  • 接下来,队列最前面的 3 个贵族(贵族 7 ,贵族 1 ,贵族 6 ) 中,舞蹈熟练度最大的人(贵族 7 )和舞蹈熟练度最小的人(贵族 1 )组队,剩下的贵族 6 移动到队尾。
  • 最后剩下的是贵族 6 ,他将和 JOI 公主一组。

贵族 6 的舞蹈熟练度为 8 ,这就是和 JOI 公主一组的贵族舞蹈熟练度最大值。

3a8912cb0aea9bf7d.png

输入样例 2

3 1
5 3
5
5

输出样例 2

5

输入样例 3

7 2
32 4
27 6
37
41
41
30
27

输出样例 3

37

数据范围与提示

对于 8\% 的数据:

  • N \leq 9

对于另 16\% 的数据:

  • N \leq 19

对于另 44\% 的数据:

  • N \leq 1999

对于 100\% 的数据,

  • 3 \leq N \le 99999
  • N 为奇数
  • 1 \leq D_i \leq 10^9 (1 \leq i \leq N)
  • 1 \leq P_i \leq N (1 \leq i \leq M)
  • P_i \not = P_j (1 \leq i\lt j \leq M)