만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

굽 있는 슬리퍼

면접 대비

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

요약
사람들의 키와 굽 높이가 주어질 때, 신발 한 켤레씩만 신고 키 T 이상이 되는 최대 인원을 구합니다.
난이도

보통10점 중 5점

유형
그리디, 정렬, 투 포인터
정답자
아직 제출이 없습니다

문제

바이토치아의 워터파크에 새 미끄럼틀이 생겼다. 안타깝게도 이 미끄럼틀은 키가 최소 TT 바이토미터 이상인 사람만 탈 수 있다.

워터파크 옆 가게에서는 굽이 달린 특수 슬리퍼를 판다. jj번째 슬리퍼 한 켤레를 신으면 키가 AjA_j 바이토미터 커진다. 키를 잴 때 슬리퍼를 벗으라고 하지 않는다. 각 사람은 최대 한 켤레만 신을 수 있다.

바이테크와 친구들은 미끄럼틀을 탈 수 있는 사람을 최대한 많이 만들려고 한다. 이를 위해 어떤 슬리퍼를 살지, 누가 어떤 켤레를 신을지 계획한다. 위생상의 이유로 슬리퍼를 신은 뒤에는 사람끼리 바꿔 신을 수 없다.

슬리퍼를 최적으로 배정했을 때 미끄럼틀을 탈 수 있는 사람 수의 최댓값을 구하는 프로그램을 작성하라.

입력

첫 줄에 자연수 NN (1≤N≤2000001 \le N \le 200000)이 주어진다. 바이테크도 포함한 그룹의 인원 수이다. 둘째 줄에는 그룹 사람들의 키 HiH_i (1≤Hi≤1091 \le H_i \le 10^9)가 NN개 공백으로 구분되어 주어진다. 셋째 줄에는 가게에 있는 슬리퍼 켤레 수 MM (0≤M≤2000000 \le M \le 200000)이 주어진다. 넷째 줄에는 가게에 있는 각 켤레의 굽 높이 AjA_j (1≤Aj≤1091 \le A_j \le 10^9)가 MM개 공백으로 구분되어 주어진다. 다섯째(마지막) 줄에는 미끄럼틀을 타기 위한 최소 키 TT (1≤T≤2⋅1091 \le T \le 2 \cdot 10^9)가 주어진다.

출력

첫 줄에 위의 조건을 지키면서 미끄럼틀을 탈 수 있는 사람 수의 최댓값을 출력한다. 값은 0 이상의 정수이다.

예제2

  1. 예제 1

    입력
    5
    5 15 10 12 1
    3
    12 2 1
    14
    
    예상 출력
    3
    
  2. 예제 2

    입력
    5
    7 3 2 5 1
    0
    
    3
    
    예상 출력
    3