Problem: Ball

In the Kingdom of IOI, a ball will be held to celebrate the birthday of Princess JOI, the princess.

N aristocrats will participate in the ball. N is an odd number. Aristocrats are numbered from 1 to N. Each aristocrat has an integer of goodness of dance, and the goodness of dance of aristocrat i (1 ≤ i ≤ N) is Di.

At the ball, N + 1 people, including Princess JOI, form a pair and dance. In the IOI Kingdom, dance groups are traditionally determined in the following ways so that advanced players can assist beginners.

* First, N aristocrats line up in a row.
* Repeat the following operations until there is only one aristocrat in the line.
--Investigate the goodness of the dance of the three aristocrats from the beginning of the line.
――Of the three aristocrats, the one with the greatest dance performance is designated as A. However, if there are multiple aristocrats, the aristocrat with the lowest number among the aristocrats with the highest dance performance is designated as A.
――Of the three aristocrats, the one with the least dance performance is called B. However, if there are multiple aristocrats, the aristocrat with the highest number among the aristocrats with the lowest dance performance is designated as B.
--A and B come out of the column and form a pair.
--The remaining one moves to the end of the line.
* Finally, the remaining one will be paired with Princess JOI.



For M aristocrats from aristocrat 1 to aristocrat M (1 ≤ M ≤ N − 2), the number in the column has already been decided in the initial state. The king is free to decide how to arrange the remaining N − M aristocrats.

Since Princess JOI has just learned to dance, the King wants to maximize the goodness of the aristocratic dance that is paired with Princess JOI. Find the maximum value that can be considered as the goodness of the aristocratic dance that is paired with Princess JOI.

Task

Given the goodness of each aristocratic dance and the place to line up in the initial state of the M aristocrats, create a program to find the maximum possible value of the goodness of the aristocratic dance paired with Princess JOI.

input

Read the following data from standard input.

* On the first line, two integers N and M are written with a blank as a delimiter. This means that there are N aristocrats participating in the ball and M aristocrats who have already decided where to line up.
* In the i-th line (1 ≤ i ≤ M) of the following M lines, two integers Di and Pi are written separated by a blank. This means that the goodness of the dance of the aristocrat i is Di, and the aristocrat i is arranged in the Pith position from the beginning of the column in the initial state.
* The integer Di + M is written on the i-th line (1 ≤ i ≤ N − M) of the following N − M lines. This means that the aristocratic (i + M) dance is Di + M.



output

On the standard output, output an integer representing the maximum value that can be considered as the goodness of the aristocratic dance paired with Princess JOI on one line.

Limits

All input data satisfy the following conditions.

* 3 ≤ N ≤ 99 999.
* N is an odd number.
* 1 ≤ M ≤ N − 2.
* 1 ≤ Di ≤ 1 000 000 000 (1 ≤ i ≤ N).
* 1 ≤ Pi ≤ N (1 ≤ i ≤ M).
* Pi ≠ Pj (1 ≤ i <j ≤ M).



Input / output example

Input example 1


7 3
5 2
5 5
8 6
6
2
8
9


Output example 1


8


In the initial state, the place where the three aristocrats line up has already been decided.

<image>
The numbers in parentheses represent the goodness of the dance. The left end is the beginning of the column.


For example, consider the case where 5 aristocrats, 1 aristocrat, 4 aristocrats, 6 aristocrats, 2 aristocrats, 3 aristocrats, and 7 aristocrats are arranged in this order from the beginning.

<image>
Arrangement after all aristocrats are lined up


In this case, the columns change as follows.

* Of the three aristocrats at the top of the line (5 aristocrats, 1 aristocrat, 4 aristocrats), the aristocrat 4 with the greatest dance performance and the aristocrat 5 with the least dance performance are paired, and the remaining aristocrat 1 is the last. Move to the tail.
* Next, among the three aristocrats at the top of the line (6 aristocrats, 2 aristocrats, 3 aristocrats), the two aristocrats who dance the most are aristocrats 6 and 3, of which the number is the smallest. The aristocrat is aristocrat 3. Of the three aristocrats at the top of the line, the aristocrat with the least dance performance is aristocrat 2. Aristocrat 3 and Aristocrat 2 form a pair, and the remaining Aristocrat 6 moves to the end.
* Next, of the three aristocrats at the top of the line (7, 1 and 6), the 7 with the greatest dance performance and the 1 with the least dance performance remained in a pair. Aristocrat 6 moves to the end.
* Eventually, 6 aristocrats will remain and will be paired with Princess JOI. The goodness of the dance of the aristocrat 6 is 8. This value is the maximum value that can be considered as the goodness of the aristocratic dance that is paired with Princess JOI.

<image>
State of change of column


Input example 2


3 1
5 3
Five
Five


Output example 2


Five


No matter what order they are lined up, Noble 2 and Princess JOI will be paired.

Input example 3


7 2
32 4
27 6
37
41
41
30
27


Output example 3


37


The question text and the data used for the automatic referee are the question text and the test data for scoring, which are created and published by the Japan Committee for Information Olympics.





Example

Input

7 3
5 2
5 5
8 6
6
2
8
9


Output

8

Solution (in CPP):

Solution:
#pragma GCC optimize ("Ofast")
#pragma GCC target ("avx")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define _USE_MATH_DEFINES
#include<iostream>
#include<string>
#include<queue>
#include<cmath>
#include<map>
#include<set>
#include<list>
#include<iomanip>
#include<vector>
#include<random>
#include<functional>
#include<algorithm>
#include<stack>
#include<cstdio>
#include<cstring>
#include<bitset>
#include<unordered_map>
#include<climits>
#include<fstream>
#include<complex>
#include<time.h>
#include<cassert>
#include<functional>
#include<numeric>
#include<tuple>

using namespace std;
using ll = long long;
using ld = long double;
#define int long long
#define all(a) (a).begin(),(a).end()
#define fs first
#define sc second
#define xx first
#define yy second.first
#define zz second.second
#define H pair<int, int>
#define P pair<int, pair<int, int>>
#define Q(i,j,k) mkp(i,mkp(j,k))
#define R pair<pair<int, int>, pair<int, int>>
#define S(i,j,k,l) mkp(mkp(i,j),mkp(k,l))
#define rep(i,n) for(int (i) = 0 ; (i) < (n) ; (i)++)
#define rng(i,s,n) for(int (i) = (s) ; (i) < (n) ; (i)++)
#define req(n,i) for(int (i) = (n) - 1 ; (i) >= 0 ; (i)--)
#define range(i,v) for(auto& (i) : v)
#define mkp make_pair
#define mem(x,k) memset(x,k,sizeof(x))
#define vec vector
#define pb emplace_back
#define lb lower_bound
#define ub upper_bound
#define crdcomp(b) sort(all((b)));(b).erase(unique(all((b))),(b).end())
#define getidx(b,i) lower_bound(all(b),(i))-b.begin()
#define ssp(i,n) (i==n-1?"\n":" ")
#define ctoi(c) (int)(c-'0')
#define itoc(c) (char)(c+'0')
#define itn int
#define pri_que priority_queue
#define pp(x,y) pb(H{x,y})
#define ppp(x,y,z) pb(Q(x,y,z))
#define pppp(x,y,z,w) pb(S(x,y,z,w))
#define cyes cout<<"Yes\n"
#define cno cout<<"No\n"
#define endl "\n"
constexpr int mod = 1e9 + 7;
constexpr int Mod = 998244353;
constexpr int MXN = 500000 + 100;
constexpr ll inf = 3 * 1e18;
constexpr int Inf = 15 * 1e8;
const vec<int>dx{ -1,1,0,0 }, dy{ 0,0,-1,1 };
template<class T>bool chmax(T& a, const T& b) { if (a < b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T& a, const T& b) { if (b < a) { a = b; return 1; } return 0; }
ll read() { ll u, k = scanf("%lld", &u); return u; }
string reads() { string s; cin >> s; return s; }
H readh(bool g = 0) { H u; ll k = scanf("%lld %lld", &u.fs, &u.sc); if (g) u.fs--, u.sc--; return u; }
void printh(H t) { printf("%lld %lld\n", t.fs, t.sc); }
bool inarea(H t, int h, int w) { return 0 <= t.fs && t.fs < h && 0 <= t.sc && t.sc < w; }
ll gcd(ll i, ll j) { return j ? gcd(j, i % j) : i; }
ll mod_pow(ll x, ll n, ll p = mod) {
	ll res = 1;
	while (n > 0) {
		if (n & 1) res = res * x % p;
		x = x * x % p;
		n >>= 1;
	}
	return res;
}//x^n%p
ll bitcount(ll x) {
	int sum = 0; for (int i = 0; i < 60; i++)if ((1ll << i) & x) sum++;
	return sum;
}
/*constexpr int fn_ = 1000005;
ll fact_[fn_], comp_[fn_];
ll comb(ll x, ll y, ll Mod = mod) {
	if (!fact_[0]) {
		fact_[0] = 1; comp_[0] = 1;
		for (int i = 1; i < fn_; i++)
			fact_[i] = fact_[i - 1] * i % Mod;
		comp_[fn_ - 1] = mod_pow(fact_[fn_ - 1], Mod - 2, Mod);
		for (int i = fn_ - 2; i > 0; i--)
			comp_[i] = comp_[i + 1] * (i + 1) % Mod;
	}
	if (x < y) return 0;
	return fact_[x] * comp_[x - y] % Mod * comp_[y] % Mod;
}*/
//--------------------------------------------------------------
int n, m;
vec<int>e[1000000];
int a[1000000];
vec<int>d;
int solve(int pos, int t) {
	if (e[pos].size() == 0) {
		if (a[pos]) {
			if (a[pos] >= t) return 0;
			else return Inf;
		}
		else return 1;
	}
	vec<int>b;
	for (auto to : e[pos]) b.pb(solve(to, t));
	sort(all(b));
	return b[0] + b[1];
}
signed main() {
	cin >> n >> m;
	rep(i, m) {
		int u, v; cin >> u >> v;
		a[v - 1] = u;
	}
	rep(i, n - m) d.pb(read());
	deque<int>dq;
	rep(i, n) dq.push_back(i);
	int idx = n;
	while (dq.size() > 1) {
		e[idx].pb(dq.front()); dq.pop_front();
		e[idx].pb(dq.front()); dq.pop_front();
		e[idx].pb(dq.front()); dq.pop_front();
		dq.push_back(idx++);
	}
	sort(all(d));
	int ok = 0, ng = Inf, mid;
	while (abs(ng - ok) > 1) {
		mid = (ok + ng) / 2;
		int sum = (n - m) - (lower_bound(all(d), mid) - d.begin());
		if (solve(idx - 1, mid) <= sum) ok = mid;
		else ng = mid;
	}
	cout << ok << endl;
}