코딩 대회

동아리에서는 수진이의 생일을 축하하려고 코딩 대회를 연다.

이 대회에는 1번부터 N번까지 번호가 붙은 N명의 코더가 참가하고, 코더 $i$에게는 코딩 실력을 나타내는 수치 $D_i$가 정해져 있다. N은 홀수이다.

대회는 두 명이 한 팀을 이루는 팀전이라서, 수진이를 포함한 N + 1명이 두 명씩 팀을 이룬다. 운영진은 팀 사이의 균형을 맞추려고 다음 방법으로 팀을 정한다.

• 먼저 N명의 참가자를 한 줄로 세운다.
• 줄에 남은 참가자가 한 명이 될 때까지 아래 과정을 반복한다.
  • 줄의 가장 앞에 선 세 명의 실력을 살펴본다.
  • 세 명 중 실력이 가장 뛰어난 사람을 뽑는다. 그런 사람이 여러 명이면 번호가 가장 작은 사람을 고른다.
  • 세 명 중 실력이 가장 모자란 사람을 뽑는다. 그런 사람이 여러 명이면 번호가 가장 큰 사람을 고른다.
  • 위에서 뽑은 두 사람을 한 팀으로 묶어 줄에서 내보낸다.
  • 남은 한 명을 줄의 가장 뒤로 보낸다.
• 마지막까지 줄에 남은 한 명이 수진이와 팀을 이룬다.

번호가 M 이하인 코더는 줄에서의 처음 위치가 이미 정해져 있다. 수진이는 남은 N - M명의 코더를 비어 있는 자리에 원하는 대로 배치할 수 있고, 실력이 최대한 뛰어난 코더와 팀을 이루고 싶어 한다. 수진이와 팀을 이루는 코더의 실력으로 가능한 값 중 최댓값을 구하는 프로그램을 작성하시오.

첫째 줄에 참가하는 코더의 수 N과 처음 위치가 정해진 코더의 수 M이 주어진다.

다음 M개 줄에는 코더 $i$의 코딩 실력 $D_i$와 처음 위치 $P_i$가 주어진다. ($1 \le i \le M$)

다음 N - M개 줄에는 코더 $i$의 코딩 실력 $D_i$가 한 줄에 하나씩 주어진다. ($M + 1 \le i \le N$)

수진이와 팀을 이루는 코더의 코딩 실력으로 가능한 값 중 최댓값을 첫째 줄에 출력한다.

• $3 \le N \le 99999$이고 N은 홀수이다.
• $1 \le M \le N - 2$
• $1 \le D_i \le 10^9$ ($1 \le i \le N$)
• $1 \le P_i \le N$ ($1 \le i \le M$)
• $i < j$이면 $P_i \ne P_j$ ($1 \le i < j \le M$)