#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <cfloat>
#include <stack>
#include <queue>
#include <vector>
#include <string>
#include <iostream>
#include <set>
#include <map>
#include <time.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;


#define NUM 500000

enum Type{
	HIGH,
	LOW,
	UNDEFINED,
};

struct Info{
	int value,loc;
};

struct Data{
	Type type;
	int need_num;
};

int N,M,length,root;
int base[100000];
int parent[NUM];
Info info[100000];
Data data[NUM];

bool is_OK(int base_value){

	int count = 0;
	for(int i = 0; i < N; i++){
		if(info[i].loc == -1 && info[i].value >= base_value)count++;
	}

	for(int i = 0; i < length; i++){
		data[i].type = UNDEFINED;
		data[i].need_num = 1;
	}

	for(int i = 0; i < N; i++){
		if(base[i] != -1){
			if(base[i] >= base_value){
				data[i].type = HIGH;
			}else{
				data[i].type = LOW;
			}
		}
	}

	int loc[3] = {0,1,2};
	int num_HIGH,num_LOW,add;
	int work[3],sum;

	while(true){

		num_HIGH = 0,num_LOW = 0;

		for(int i = 0; i < 3; i++){
			if(data[loc[i]].type == HIGH){
				num_HIGH++;
			}else if(data[loc[i]].type == LOW){
				num_LOW++;
			}
		}

		if(num_HIGH >=2){

			data[parent[loc[0]]].type = HIGH;
			data[parent[loc[0]]].need_num = 0;

		}else if(num_LOW >= 2){

			data[parent[loc[0]]].type = LOW;
			data[parent[loc[0]]].need_num = 0;

		}else{
			add = 2-num_HIGH;

			for(int i = 0; i < 3; i++)work[i] = BIG_NUM;

			for(int i = 0; i < 3; i++){
				if(data[loc[i]].type == UNDEFINED){
					work[i] = data[loc[i]].need_num;
				}
			}

			sort(work,work+3);

			sum = 0;
			for(int i = 0; i < add; i++)sum += work[i];

			data[parent[loc[0]]].need_num = sum;
		}

		if(parent[loc[0]] == root)break;

		for(int i = 0; i < 3; i++){
			loc[i] += 3;
		}
	}

	if(data[root].type == HIGH)return true;
	if(data[root].type == LOW)return false;

	return count >= data[root].need_num;
}

int main(){

	scanf("%d %d",&N,&M);

	for(int i = 0; i < N; i++){
		base[i] = -1;
		info[i].loc = -1;
	}

	int maximum = 0,minimum = BIG_NUM;

	for(int i = 0; i < M; i++){
		scanf("%d %d",&info[i].value,&info[i].loc);
		info[i].loc--;
		base[info[i].loc] = info[i].value;
		maximum = max(maximum,info[i].value);
		minimum = min(minimum,info[i].value);
	}

	for(int i = 0; i < N-M; i++){
		scanf("%d",&info[M+i].value);
		maximum = max(maximum,info[M+i].value);
		minimum = min(minimum,info[M+i].value);
	}

	for(int i = 0; i < NUM; i++){
		parent[i] = -1;
	}

	int index = N;
	queue<int> Q;
	for(int i = 0; i < N; i++){
		Q.push(i);
	}

	int A,B,C;

	while(Q.size() != 1){
		A = Q.front();
		Q.pop();
		B = Q.front();
		Q.pop();
		C = Q.front();
		Q.pop();

		parent[A] = index;
		parent[B] = index;
		parent[C] = index;

		Q.push(index);
		index++;
	}

	length = index;
	index--;
	root = index;

	int left = minimum,right = maximum,m = (left+right)/2;
	int ans = minimum;

	while(left <= right){
		if(is_OK(m)){
			ans = m;
			left = m+1;
		}else{
			right = m-1;
		}
		m = (left+right)/2;
	}

	printf("%d\n",ans);

	return 0;
}

