首先二分一个答案x，然后我们把>=x的数看成1,<x的数看成0，那如果最后剩下1，这个答案就是合法的。
那我们就来算让某一位得1至少需要填几个1（设这个值是f[i]）
i=1..n时，显然，如果i已经固定，f[i]=0或inf（取决于原来是1还是0）；如果i还没有固定，那f[i]=1
然后每次就可以由前三个转移到最后一个，也就是取这三个中f[i]较小的两个相加（转移过去的是1，当且仅当3个里有至少2个1）
这个转移和队列很像，所以可以直接用队列维护。
最后我们看f[最后那位数]是否多于还没填的1的数量就完事了。
#include<bits/stdc++.h>
#define pa pair<int,int>
#define ll long long
using namespace std;
const int maxn=,inf=0x3f3f3f3f; ll rd(){
ll x=;char c=getchar();int neg=;
while(c<''||c>''){if(c=='-') neg=-;c=getchar();}
while(c>=''&&c<='') x=x*+c-'',c=getchar();
return x*neg;
} int N,M,num[maxn],num2[maxn],val[maxn];
queue<int> q; inline bool judge(int x){
int n=;
for(int i=;i<=N-M;i++) if(num2[i]>=x) n++;
for(int i=;i<=N;i++) q.push(num[i]?(num[i]>=x?:inf):);
while(!q.empty()){
int a,b,c;
a=q.front();q.pop();if(q.empty()) return a<=n;
b=q.front();q.pop();c=q.front();q.pop();
q.push(min(inf,min(a+b,min(a+c,b+c))));
}
} int main(){
int i,j,k;
N=rd(),M=rd();
for(i=;i<=M;i++){
j=rd(),k=rd();num[k]=val[i]=j;
}for(i=;i<=N-M;i++) val[i+M]=num2[i]=rd();
sort(val+,val+N+);
int l=,r=N;
while(l<=r){
int m=l+r>>;
if(judge(val[m])) l=m+;
else r=m-;
}printf("%d\n",val[l-]);
return ;
}