Ball

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.

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.

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.

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

inputFormat

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.

outputFormat

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.

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.

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.

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

样例

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

8