/*input
15 1
781314749 1
312224898
269509097
255956030
898895737
228424650
553611871
905685626
332572742
398251511
103523987
310943411
741678005
214559293
439294954
*/
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <utility>
#include <vector>
using namespace std;
#define sp ' '
#define endl '\n'
#define fi first
#define se second
#define mp make_pair
#define int long long
#define N 200005
#define bit(x,y) ((x>>y)&1LL)
#define show(x) cout << (#x) << ": " << x << endl;
#define ii pair<int,int>
ostream& operator << (ostream &os, vector<int>&x) {
	for (int i = 0; i < x.size(); i++) os << x[i] << sp;
	return os;
}
ostream& operator << (ostream &os, pair<int, int> x) {
	cout << x.fi << sp << x.se << sp;
	return os;
}
ostream& operator << (ostream &os, vector<pair<int, int> >&x) {
	for (int i = 0; i < x.size(); i++) os << x[i] << endl;
	return os;
}

int n, m;
int peak;
vector<vector<int> > a(N);
int root = 0;
int cnt[2];
vector<int> allval;
int valPos[N];
vector<vector<int> > dp;
void addEdge(int x, int y) {
	a[x].push_back(y);
}

void createEdge(vector<int> cur) {
	if (cur.size() == 1) {
		root = cur.front();
		return;
	}
	vector<int> nxt;
	while (cur.size() % 3 != 0) {
		nxt.push_back(cur.back());
		cur.pop_back();
	}
	reverse(cur.begin(), cur.end());
	while (!cur.empty()) {
		nxt.push_back(++peak);
		for (int i = 1; i <= 3; i++) {
			addEdge(peak, cur.back()); cur.pop_back();
		}
	}
	createEdge(nxt);
}

int cal(int u, int wh, const int lim) {
	int &ret = dp[u][wh];
	if (ret != -1) return ret;
	ret = 1e18;
	if (u <= n) {
		if (valPos[u] == -1) return ret = wh;
		int x; if (valPos[u] < lim) x = 0; else x = 1;
		if (wh == x) return ret = wh;
		else return ret;
	}
	else {
		if (a[u].size() == 1)
			return ret = cal(a[u].front(), wh, lim);
		for (int mask = 0; mask < (1 << 3); mask++) {
			int num1 = __builtin_popcount(mask); int num0 = 3 - num1;
			if ((wh == 0 && num0 > num1) || (wh == 1 && num0 < num1)) {
				int sum = 0;
				for (int i = 0; i < 3; i++)
					sum += cal(a[u][i], bit(mask, i), lim);
				ret = min(ret, sum);
			}
		}
		return ret;
	}
}

bool check(int lim) {
	memset(cnt, 0, sizeof(cnt));
	for (auto u : allval) {
		if (u < lim) cnt[0]++;
		else cnt[1]++;
	}
	dp.assign(root + 5, vector<int>(2, -1));
	int rec = cal(root, 1, lim);
	return rec <= cnt[1];
}

signed main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> n >> m; peak = n;
	vector<int> sta; for (int i = 1; i <= n; i++) sta.push_back(i);
	createEdge(sta); memset(valPos, -1, sizeof(valPos));
	for (int i = 1; i <= m; i++) {
		int x, y; cin >> x >> y;
		valPos[y] = x; allval.push_back(x);
	}
	for (int i = 1; i <= n - m; i++) {
		int x; cin >> x; allval.push_back(x);
	}
	sort(allval.begin(), allval.end());
	int l = 0, r = allval.size() - 1;
	while (l != r) {
		int mid = (l + r + 1) / 2;
		if (check(allval[mid])) l = mid;
		else r = mid - 1;
	}
	cout << allval[l] << endl;
}

Measured memory_bytes: 21148