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 JAVA):

Solution:
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;

public class Main {
	static boolean debug = false;

	public static void main(String[] args) throws IOException {

		UserScanner scan = new UserScanner(System.in);
		PrintWriter pwriter = new PrintWriter(System.out);

		int n = scan.nextInt();
		int m = scan.nextInt();
		Ball ball = new Ball(n, m, debug);

		for (int i = 0; i < m; i++)
			ball.setDancePosition(scan.nextInt(), scan.nextInt());
		for (int i = 0; i < n - m; i++)
			ball.setDance(scan.nextInt());

		pwriter.println(ball.getMaxDance());

		pwriter.flush();

		scan.close();
		System.exit(0);
	}
}

class Ball {
	boolean debug;

	class Gr {
		int[] ch = new int[3]; // if leaf is true, then set dance skill,
								// otherwise child group number
		boolean[] leaf = new boolean[3];
	}

	Gr[] gr;
	int root;

	int[] pool;
	int px = 0;
	int[] allNoble;
	int ax = 0;

	public Ball(int n, int m, boolean debug) {
		this.debug = debug;
		// number of group is N/3 + N/3/3 + N/3/3/3 + ... <= N/2
		gr = new Gr[(n / 2) + 1];
		root = -1;
		int c = 0, p = 0;
		for (int i = 0; root == -1; i++) {
			gr[i] = new Gr();
			for (int j = 0; j < 3; j++)
				if (c < n) {
					gr[i].leaf[j] = true;
					gr[i].ch[j] = -1;
					c++;
				} else if (p == i)
					root = i - 1;
				else {
					gr[i].leaf[j] = false;
					gr[i].ch[j] = p++;
				}
		}

		pool = new int[n - m];
		allNoble = new int[n];
	}

	public int getMaxDance() {
		if (debug)
			printGr(root);

		Arrays.sort(pool); // not allocated nobles
		Arrays.sort(allNoble);
		if (debug)
			for (int i = 0; i < allNoble.length; i++)
				System.out.println("noble " + i + ", d=" + allNoble[i]);

		int hi = 1;
		for (int i = allNoble.length / 3; i > 0; i /= 3)
			hi *= 2; // possible best dancer, if 3 persons then 2nd, if 9
						// persons then 4th, if 27 persons 8th is possible.
						// (it's not accurate)
		hi = allNoble.length - hi;
		int lo = 0, maxDance = -1, midDance = -1;
		boolean down = true;

		while (hi >= lo) { // search max dance skill
			int mid = lo + (hi - lo) / 2;
			if (debug)
				System.out.println("hi=" + hi + ", lo=" + lo + ", mid=" + mid);
			if (midDance == allNoble[mid])
				if (down) {
					hi = mid - 1;
					continue;
				} else {
					lo = mid + 1;
					continue;
				}

			midDance = allNoble[mid];
			if (isPossible(midDance, getPoolNoble(midDance))) {
				// if it possible to assign this dance skill
				// check more higher
				maxDance = midDance;
				down = false;
				lo = mid + 1;
			} else {
				down = true;
				hi = mid - 1;
			}
		}

		return maxDance;
	}

	private boolean isPossible(int d, int f) {
		if (debug)
			System.out.println("d=" + d + ", f=" + f + ", demand=" + getLeastNoble(root, d));

		// dance skill d, and f is free nobles which have dance skill >= d
		if (getLeastNoble(root, d) <= f)
			return true;
		else
			return false;
	}

	private int getLeastNoble(int p, int d) {
		// count the noble which are required to allocate
		int[] a = new int[3];
		for (int i = 0; i < 3; i++)
			if (gr[p].leaf[i])
				if (gr[p].ch[i] >= d)
					a[i] = 0; // already allocated
				else if (gr[p].ch[i] > 0)
					a[i] = pool.length + 1; // sign for not applicable
				else
					a[i] = 1; // need to allocate
			else
				a[i] = getLeastNoble(gr[p].ch[i], d); // child group check by
														// recursive

		// need 2 nobles (highest skill and middle)
		return Math.min(pool.length + 1, a[0] + a[1] + a[2] - Math.max(a[0], Math.max(a[1], a[2])));

	}

	private int getPoolNoble(int d) {
		// count free nobles which have higher dance skill
		if (pool[0] >= d)
			return pool.length;
		if (pool[pool.length - 1] < d)
			return 0;
		return getPoolN(d, 0, pool.length);
	}

	private int getPoolN(int d, int lo, int hi) {
		if (hi <= lo)
			if (pool[lo] >= d)
				return pool.length - lo;
			else
				return pool.length - lo - 1;
		int mid = lo + (hi - lo) / 2;
		if (pool[mid] >= d)
			return getPoolN(d, lo, mid);
		else
			return getPoolN(d, lo + (hi - lo + 1) / 2, hi);
	}

	public void setDance(int d) {
		pool[px++] = d;
		allNoble[ax++] = d;
	}

	public void setDancePosition(int d, int p) {
		p--;
		gr[p / 3].ch[p % 3] = d;
		allNoble[ax++] = d;
	}

	private void printGr(int p) {
		System.out.println(" Gr=" + p);
		System.out.print("   ");
		if (gr[p].leaf[0])
			System.out.print(gr[p].ch[0]);
		else
			System.out.print("Gr=" + gr[p].ch[0]);
		if (gr[p].leaf[1])
			System.out.print(", " + gr[p].ch[1]);
		else
			System.out.print(", Gr=" + gr[p].ch[1]);
		if (gr[p].leaf[2])
			System.out.print(", " + gr[p].ch[2]);
		else
			System.out.print(", Gr=" + gr[p].ch[2]);
		System.out.println();
		if (!gr[p].leaf[0])
			printGr(gr[p].ch[0]);
		if (!gr[p].leaf[1])
			printGr(gr[p].ch[1]);
		if (!gr[p].leaf[2])
			printGr(gr[p].ch[2]);
	}

}

class UserScanner {
	private InputStream in;
	private final byte[] buffer = new byte[1024];
	private int ptr = 0;
	private int buflen = 0;

	public UserScanner(InputStream inStream) {
		in = inStream;
	}

	private void read() {
		ptr = 0;
		try {
			buflen = in.read(buffer);
		} catch (IOException e) {
			e.printStackTrace();
			System.exit(9);
		}
	}

	private byte getByte() {
		if (ptr >= buflen)
			read();
		if (buflen < 0 || isCtlSpace(buffer[ptr])) {
			return -1;
		} else
			return buffer[ptr++];
	}

	private void skipCtlSpace() {
		for (; ptr < buflen; ptr++)
			if (!isCtlSpace(buffer[ptr]))
				return;
		read();
		skipCtlSpace();
	}

	private boolean isCtlSpace(byte b) {
		if (b <= ' ' || b > '~')
			return true;
		else
			return false;
	}

	public void close() {
		try {
			in.close();
		} catch (IOException e) {
			e.printStackTrace();
			System.exit(9);
		}
	}

	public String next() {
		skipCtlSpace();
		StringBuilder sb = new StringBuilder();
		byte b;
		while ((b = getByte()) != -1) {
			sb.appendCodePoint(b);
		}
		return sb.toString();
	}

	public int nextInt() {
		skipCtlSpace();
		int n = 0;
		boolean minus = false;
		byte b;
		while ((b = getByte()) != -1) {
			if (b == '-')
				minus = true;
			else {
				n *= 10;
				n += (b - '0');
			}
		}
		if (minus)
			return n * -1;
		else
			return n;
	}
}