#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> p;
typedef double db;

#define fr first
#define sc second
#define pb push_back
#define rep(i,x) for(ll i=0;i<x;i++)
#define rep1(i,x) for(ll i=1;i<=x;i++)
#define rrep(i,x) for(ll i=x-1;i>=0;i--)
#define rrep1(i,x) for(ll i=x;i>0;i--)
struct T{
	ll dance,id;
	bool operator<(const T an)const{
		return dance!=an.dance?dance<an.dance:id>an.id;
	}
	bool operator>(const T an)const{
		return dance!=an.dance?dance>an.dance:id<an.id;
	}
	bool operator==(const T an)const{
		return dance==an.dance&&id==an.id;
	}
};
const ll INF=0xffffffffffff;
ll N,M,D[100000],P[100000];
ll tmpl[100000];//?????¨?????¨?????????
vector<T> ds;
ll cnt;
bool ok(ll X){//X??\????????§?????????
	cnt=0;
	queue<ll> q;
	rep(i,N){
		if(tmpl[i]==-1) q.push(1); 
		else if(tmpl[i]>=X){
			q.push(0);
			cnt++;
		}
		else q.push(INF);
	}
	while(q.size()!=1){
		ll a,b,c;
		a=q.front();
		q.pop();
		b=q.front();
		q.pop();
		c=q.front();
		q.pop();
		if(b>c) swap(b,c);
		if(a>c) swap(a,c);
		q.push(min(a+b,INF));
	}
	//cout<<X<<" "<<q.front()<<" "<<N-M<<endl;
	return q.front()<=N-X-cnt;
}


int main()
{
	cin>>N>>M;
	rep(i,M){
		cin>>D[i]>>P[i];
		P[i]--;
		ds.pb(T{D[i],i});
	}
	rep(i,N-M){
		cin>>D[M+i];
		ds.pb(T{D[M+i],M+i});
	}
	sort(ds.begin(),ds.end());
	//ds.erase(unique(ds.begin(),ds.end()),ds.end());
	rep(i,N){
		D[i]=lower_bound(ds.begin(),ds.end(),T{D[i],i})-ds.begin();
	}
	memset(tmpl,-1,sizeof(tmpl));
	rep(i,M){
		tmpl[P[i]]=D[i];
	}
	ll lb=0,ub=N;
	while(ub-lb>1){
		ll mid=(ub+lb)/2;
		if(ok(mid)) lb=mid;
		else ub=mid;
	}
	cout<<ds[lb].dance<<endl;
}