선물 고르기

• 상황을 정리해보면 답은 굉장히 간단하다. 내 상자 크기보다 작은 선물 중에서 가장 큰 것이 답이다.
• 우선, 상자와 선물이 다 정렬되어있다고 생각하자
  • B[0]>=B[1]>=B[2]>= … >= B[N-1]
  • A[0]>=A[1]>=A[2]>= … >= A[N-1]
• 모든 선물을 모든 상자에 넣을 수 있는 방법이 최소 한가지는 있다. 그렇다면, 적어도, 상자와 선물을 순위대로 매칭했을때는 선물들이 상자에 모두 들어갈수 있어야 한다. 다시 말하면 B[0]>=A[0], B[1]>=A[1], …, B[N-1]>=A[N-1] 이다
• 이제 내 차례에 i번 상자를 고르게 되는 상황이라 하자. 이 말은 앞선 K명이 상자를 가져가는 동안 0번부터 i-1번 상자를 다 가져가버렸다는 말이다. i번 상자에 들어갈 수 있는 가장 큰 선물의 번호가 j번이라고 하자 (A[j-1]>B[i]>=A[j]). 0번부터 i-1번 상자들에 다음과 같이 선물이 담겨있었다면, i번째 상자에 j번 선물이 들어있을 수 있다.
  • j번 상자보다 큰 상자들에는 같은 순위의 선물들이 들어있었고, j번부터 i-1번까지의 상자들에는 한 순위 더 작은 선물이 담겨있었다면, j번 선물과 i번 상자가 남아 있을 것이다.
  • B[0]>=A[0], B[1]>=A[1], …, B[j-1]>=A[j-1] 이고 B[j]>=A[j+1], …., B[i-1]⇒A[i] 이므로 가능하다
  • 이제 B[i] ⇒ A[j] 이므로 i번 상자에 j번 선물을 담으면 된다.
• 나머지 선물과 상자들은 다시 크기 순서대로 매칭됐다고 생각하면 된다
• 결국, 내가 선택하게 되는 선물상자의 크기가 얼마인지, 그리고 그 상자안에 들어갈수 있는 가장 큰 선물이 무엇인지만 찾으면 된다.
• 둘다 그냥 O(n)에 찾을 수 있다. 태그에는 이분탐색이나 BST 가 포함되어 있는데, 아마도 상자안에 들어갈 수 있는 가장 큰 선물이 무엇인지를 찾기 위해서 정렬후 이분탐색이나 BBST등을 사용해야 한다고 생각한것 같다. 그러나, 단 한번의 쿼리만 처리하면 되기 때문에 그냥 모든 원소를 훑으면서 O(n)에 찾으면 충분하다.

"""Solution code for "BOJ 32374. 선물 고르기".

- Problem link: https://www.acmicpc.net/problem/32374
- Solution link: http://www.teferi.net/ps/problems/boj/32374
"""

import collections
import sys


def main():
    # pylint: disable-next=unused-variable
    N, K = [int(x) for x in sys.stdin.readline().split()]
    A = [int(x) for x in sys.stdin.readline().split()]
    B = [int(x) for x in sys.stdin.readline().split()]
    C = [int(x) for x in sys.stdin.readline().split()]

    counter = collections.Counter(B)
    counter.subtract(C)
    box = max(+counter)
    answer = max(a_i for a_i in A if a_i <= box)

    print(answer)


if __name__ == '__main__':
    main()