BOJ에서는 수진이의 생일을 축하하기 위한 코딩 대회를 열기로 하였다.

이 대회에는 1부터 N까지 번호가 붙은 N명의 코더들이 참가할 예정이며, 그들에겐 각각 코딩 실력을 나타내는 수치가 정해져있다. (N은 홀수이고 코더 i의 코딩 실력은 D_i이다)

대회는 2명이 짝을 이루어나가는 팀전이므로 수진이를 포함한 N + 1명의 코더들은 2명씩 팀을 이루게 된다. 팀간의 밸런스를 맞추기로한 BOJ에서는 아래와 같은 방법을 이용하여 팀을 정하기로 했다.

• 먼저, N명의 참가자를 1줄로 세운다.
• 줄에 남아있는 참가자가 1명이 될 때가지, 이하의 과정을 반복한다.
  • 가장 앞에 서있는 3명의 참가자의 실력을 조사한다.
  • 3명의 참가자 중, 가장 실력이 뛰어난 사람을 뽑는다. 실력이 뛰어난 사람이 여러명일 경우, 번호가 가장 작은 사람을 선택한다.
  • 3명의 참가자 중, 가장 실력이 부족한 사람을 뽑는다. 실력이 부족한 사람이 여러명일 경우, 번호가 가장 큰 사람을 선택한다.
  • 위에서 선택한 두 사람을 한 팀으로 한다.
  • 남은 한 명의 참가자를 줄의 가장 뒤로 보낸다.
  </ul> </li>
  • 마지막에 남은 1명이 수진이와 팀을 이룬다!

  번호가 M 이하인 코더들은 이미 줄에서의 초기 위치가 정해져있다. (1≦M≦N-2) 코딩 초보 수진이는 남은 N - M명의 코더들의 위치를 조정하여 최대한 코딩 실력이 뛰어난 코더와 팀을 이루고 싶어한다. 수진이를 위해 수진이와 팀을 이룰 수 있는 코더의 코딩 실력으로 가능한 것 중 최댓값을 계산하는 프로그램을 만들어주자.

  입력 형식

  데이터의 입력은 아래와 같다.

  • 1행에는 참가하는 코더의 수 N과 초기 위치가 정해진 코더의 수 M이 주어진다.
  • 이은 M열에는 코더 i의 코딩 실력 D_i와 초기 위치 P_i가 주어진다. (1 ≦ i ≦ M)
  • 이은 N - M열에는 코더 i의 코딩 실력 D_i가 주어진다. (M+1 ≦ i ≦ N)

  출력 형식

  수진이와 팀을 이루는 코더의 코딩 실력으로 가능한 값 중 최대치를 출력한다.

  예제 입력 1

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

  예제 출력 1

  8

  예제 입력 2

  3 1
  5 3
  5
  5

  예제 출력 2

  5

  예제 입력 3

  7 2
  32 4
  27 6
  37
  41
  41
  30
  27

  예제 출력 3

  37