선물 고르기

시간 제한2초메모리 제한1024 MB

요약
선물 크기, 상자 크기, 앞선 K명이 가져간 상자 크기가 주어질 때, 당신이 가져갈 수 있는 선물 크기의 최댓값을 구한다.
난이도

보통10점 중 6점

유형
정렬, 그리디, 이분 탐색
정답자
아직 제출이 없습니다

문제

축하합니다! 당신은 INU 코드페스티벌 2024에서 특별상을 받은 NN명 중 한 명으로 선정되었습니다!

특별상을 받는 모든 수상자는, 순서대로 무대에 올라와 선물 상자 중 하나를 골라 가져가게 됩니다. 이때, 앞의 사람들이 이미 가져간 상자는 고를 수 없습니다.

각 선물 상자에는 선물 상자의 크기보다 작거나 같은 선물이 들어있습니다. 선물 상자의 크기와 안에 담긴 선물의 가치가 반드시 비례하는 것은 아니지만, 당신은 상자가 클수록 더 좋은 선물이 들어있을 것이라고 믿고 있습니다. 그래서 남아 있는 상자 중 가장 큰 크기의 상자를 고르려고 합니다.

당신의 앞에 KK명의 특별상 수상자가 선물 상자를 골라 가져갔고, 이제 드디어 당신의 차례입니다.

당신이 남은 선물 상자 중 가장 큰 선물 상자를 골랐을 때, 가져갈 가능성이 있는 가장 큰 선물의 크기는 무엇일까요?

입력

첫 번째 줄에 선물의 개수 N(2≤N≤200,000)N(2\leq N \leq 200\\,000)과 먼저 선물 상자를 가져간 사람의 수 K(1≤K<N)K(1\leq K < N)가 공백으로 구분되어 주어집니다.

두 번째 줄에 NN개의 정수 A_1,A_2,...,A_NA\_1, A\_2, ..., A\_N이 공백으로 구분되어 주어집니다. (1≤A_i≤109)(1 \leq A\_i \leq 10^9) A_iA\_i는 ii 번째 선물의 크기입니다.

세 번째 줄에 NN개의 정수 B_1,B_2,...,B_NB\_1, B\_2, ..., B\_N이 공백으로 구분되어 주어집니다. (1≤B_i≤109)(1 \leq B\_i \leq 10^9) B_iB\_i는 ii 번째 선물 상자의 크기입니다.

ii번째 선물이 ii번째 선물 상자에 들어있지 않을 수 있음에 유의해주세요.

네 번째 줄에 KK개의 정수 C_1,C_2,...,C_KC\_1, C\_2, ..., C\_K가 공백으로 구분되어 주어집니다. (1≤C_i≤109)(1 \leq C\_i \leq 10^9) C_iC\_i는 당신 앞의 ii 번째 사람이 골라간 선물 상자의 크기입니다.

선물 상자에 모든 선물을 담을 수 없거나, KK명의 사람이 실제로 가져갈 수 없는 크기의 선물 상자를 가져가는 경우는 입력으로 주어지지 않음이 보장됩니다.

출력

가능한 모든 경우 중, 당신이 가져갈 수 있는 선물 크기의 최댓값을 출력해주세요.

힌트

실제 특별상 추첨은 제비뽑기로 진행됩니다.

예제1

  1. 예제 1

    입력
    7 3
11 3 5 13 9 1 7
1 9 6 9 13 13 5
13 9 13
    예상 출력
    9