#include <bits/stdc++.h>
using namespace std;

const int maxn = (int) 4e5 + 5;
const int inf = 1e9;

int n, m, root;
vector<int> G[maxn];
int d[maxn], p[maxn];
int a[maxn];
int dp[maxn];

void dfs(int u) {
    if(G[u].size() == 0) {
        if(a[u] == -1) {
            dp[u] = 1;
            return ;
        }
        else if(a[u] == 0) dp[u] = maxn;
        else dp[u] = 0;
        return ;
    }
    int x = G[u][0];
    int y = G[u][1];
    int z = G[u][2];
    dfs(x);
    dfs(y);
    dfs(z);

    dp[u] = maxn;
    dp[u] = min(dp[u], dp[x] + dp[y]);
    dp[u] = min(dp[u], dp[y] + dp[z]);
    dp[u] = min(dp[u], dp[z] + dp[x]);
}

bool check(int x) {
    int cnt = 0;
    for (int i = 1; i <= n; i ++) a[i] = -1;
    for (int i = 1; i <= m; i ++) {
        a[p[i]] = (d[i] >= x);
    }
    for (int i = m + 1; i <= n; i ++) {
        cnt += (d[i] >= x);
    }
    dfs(root);
    if(dp[root] <= cnt) return 1;
    else return 0;
}



int main() {
    ///freopen("test.txt", "r", stdin);
    ios_base::sync_with_stdio(0);
    cin >> n >> m;
    for (int i = 1; i <= m; i ++) {
        cin >> d[i] >> p[i];
    }
    for (int i = m + 1; i <= n; i ++) {
        cin >> d[i];
    }
    queue <int> Q;
    deque<int> dq;
    for (int i = 1; i <= n; i ++) Q.push(i);
    root = n;
    while(Q.size() > 1){
        root++;
        for(int i = 1 ; i <= 3 ; i++){
            int u = Q.front() ; G[root].push_back(u) ; Q.pop();
        }
        Q.push(root);
    }
    int lo = 0;
    int hi = (int) 1e9 + 7;
    int res;
    while (lo <= hi) {
        int mid = (lo + hi) >> 1;
        if(check(mid)) {
            res =  mid;
            lo = mid + 1;
        }
        else {
            hi = mid - 1;
        }
    }
    ///for (int i = 0; i < G[8].size(); i ++) cout << G[8][i] << ' ';
    ///cout << endl;
    ///cout << check() << endl;
    cout << res << endl;
}