시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 19 13 11 68.750%

문제

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

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

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

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

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

입력

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

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

각 데이터의 범위는 아래와 같다.

  • 3≦N≦99999 (N은 홀수)
  • 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)

출력

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

예제 입력

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

예제 출력

8

예제 입력 2

3 1
5 3
5
5

예제 출력 2

5

예제 입력 3

7 2
32 4
27 6
37
41
41
30
27

예제 출력 3

37

힌트

출처

Olympiad > 일본정보올림피아드 > JOI 2015 4번

  • 문제를 번역한 사람: sujin