import core.stdc.stdio;
import std.algorithm;
import std.stdio;

int lowerBound(int[] data,int t){
	int l=0;
	int r=cast(int)data.length+1;
	while(r-l>1){
		int m=(l+r)/2;
		if(data[m-1]<t)
			l=m;
		else
			r=m;
	}
	return l;
}

void main(){
	int n,m;
	scanf("%d%d",&n,&m);
	int[] u = new int[n];
	int[] k = new int[n];
	foreach(i;0..m){
		scanf("%d",&u[i]);
		int j;
		scanf("%d",&j);
		k[--j]=u[i];
	}
	foreach(i;m..n)
		scanf("%d",&u[i]);
	sort(u);
	int[] d=new int[n*2];
	static immutable int inf = 114514;
	bool Solve(int t){
		int c=n-u.lowerBound(t);
		foreach(i;0..n)
			if(k[i])
				if(k[i]>=t){
					d[i]=0;
					c--;
				}else
					d[i]=inf;
			else
				d[i]=1;
		int b=0,e=n;
		while(b<e-1){
			d[e++]=min(inf,d[b]+d[b+1]+d[b+2]-max(d[b],d[b+1],d[b+2]));
			b+=3;
		}
		return d[e-1]<=c;
	}
	int l=0,r=n;
	while(r-l>1){
		int s=(r+l)/2;
		if(Solve(u[s]))
			l=s;
		else
			r=s;
	}
	printf("%d\n",u[l]);
}