#include <bits/stdc++.h>
using namespace std;
int X[99999],DP[2000000];
vector<int> Y,E[2000000];
int main() {
    int N,M;
    scanf("%d %d",&N,&M);
    for(int i=0;i<M;i++) {
          int D,P;
          scanf("%d %d",&D,&P);P--;
          X[P]=D;
    }
    for(int i=M;i<N;i++) {
        int D;
        scanf("%d",&D);
        Y.push_back(D);
    }
    int k=N;
    for(int i=0;i+3<=k;i+=3) {
        E[k].push_back(i);
        E[k].push_back(i+1);
        E[k].push_back(i+2);
        k++;
    }
    int l=0,r=1000000001;
    while(r-l>1) {
        int m=(l+r)/2;
        int high=0;
        for(int i=0;i<Y.size();i++) {
            if(Y[i]>=m) high++;
        }
        fill(DP,DP+2000000,1<<25);
        for(int i=0;i<k;i++) {
            if(i<N) {
                if(X[i]==0) {
                    DP[i]=1;
                }else if(X[i]>=m) {
                    DP[i]=0;
                }
            }else {
                int a=DP[E[i][0]];
                int b=DP[E[i][1]];
                int c=DP[E[i][2]];
                DP[i]=a+b+c-max(a,max(b,c));
            }
        }
        if(DP[k-1]<=high) l=m; else r=m;
    }
    printf("%d\n",l);
}