#include <bits/stdc++.h>

using namespace std;

#define int ll

typedef long long ll;
typedef pair<int, int> P;

const int inf = 1e9+2;

int N;
vector<int> v;
vector<int> can;
vector<P> pre;

int need(int l, int r, int th) {
	if (r-l == 1) {
		if (v[l] >= 0) {
			return v[l] >= th ? 0 : inf;
		}
		else {
			return 1;
		}
	}
	else {
//		assert( (r - l) % 3 == 0 );
		int d = (r - l) / 3;
		vector<int> a(3);
		for (int i = 0; i < 3; ++i) {
			a[i] = need(l + d * i, l + d * (i+1), th);
		}
		sort(a.begin(), a.end());
		return a[0] + a[1];
	}
}
signed main() {
	int M; cin >> N >> M;
	for (int i = 0; i < M; ++i) {
		int D, p; cin >> D >> p; --p;
		pre.push_back( P(D, p) );
	}
	for (int i = 0; i < N-M; ++i) {
		int D; cin >> D;
		pre.push_back( P(D, -1) );
	}

	int tN; for (tN = 1; tN < N; tN *= 3);
	for (int i = 0; i < N; ++i) {
		if (pre[i].second >= 0) {
			pre[i].second += (tN - N) / 2 * 3;
			if (pre[i].second >= tN) {
				pre[i].second = (pre[i].second-tN) * 3 + 2;
			}
		}
	}
	for (int i = 0; i < (tN-N)/2; ++i) {
		pre.push_back( P(0, i*3) );
		pre.push_back( P(inf, i*3+1) );
	}
	sort( pre.begin(), pre.end() );

	N = tN; v = vector<int>(N, -1);
	for (int i = 0; i < (int)pre.size(); ++i) {
		if (pre[i].second >= 0) {
			assert(v[pre[i].second] == -1);
			v[pre[i].second] = pre[i].first;
		}
		else {
			can.push_back(pre[i].first);
		}
	}
	sort(can.begin(), can.end());

	int cnt = 0;
	for (int i = 0; i < v.size(); ++i) {
		if (v[i] == -1) ++cnt;
	}
	assert( cnt == can.size() );

	ll l = 1, r = inf;
	for (int t = 0; t < 100; ++t) {
		int m = (l + r) / 2;
		int rest = (int)can.size() - (int)(lower_bound( can.begin(), can.end(), m ) - can.begin());
		if ( need(0, N, m) <= rest ) {
			l = m;
		}
		else {
			r = m;
		}
	}
	assert( r - l <= 1 );
	cout << l << endl;
}