아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

Klapki na obcasach

면접 대비

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

요약
한 쌍의 클랙스를 한 사람에게만 배정해 키와 굽 높이의 합이 T 이상이 되게 할 때, 탈 수 있는 사람 수의 최댓값을 구한다.
난이도

보통10점 중 5점

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

문제

W Bajtocji powstał właśnie nowy aquapark, a w nim zjeżdżalnia. Niestety, do zjazdu z tej zjezdżalni dopuszczone są tylko osoby mające co najmniej T bajtometrów wzrostu.

Na szczęście w sklepie przy aquaparku można kupić specjalne klapki na obcasach. Założenie j-tej pary klapek powoduje, że staje się wyższym o Aj bajtometrów, a do pomiaru wzrostu nikt przecież klapek zdejmować nie każe. Rzecz jasna, każda osoba może założyć co najwyżej jedną parę klapek.

Bajtek wraz z grupą przyjaciół chcą teraz mądrze rozplanować, jakie klapki należy kupić i założyć, aby jak najwięcej osób mogło zjechać ze zjeżdżalni. Ze względów higienicznych osoby nie mogą się po założeniu wymieniać klapkami.

Napisz program, który wyznaczy największą liczbę osób jakie mogą zjechać ze zjeżdżalni (dla optymalnego rozplanowania klapek).

입력

W pierwszym wierszu wejścia znajduje się jedna liczba naturalna N (1 ≤ N ≤ 200 000) określająca liczbę osób w grupie (razem z Bajtkiem). W drugim wierszu znajduje się ciąg N liczb naturalnych Hi (1 ≤ Hi ≤ 109) pooddzielanych pojedynczymi odstępami. Są to wzrosty kolejnych osób w grupie. W trzecim wierszu wejścia znajduje się jedna nieujemna liczba całkowita M (0 ≤ M ≤ 200 000) określająca liczbę par klapek, które są dostępne w sklepie. W czwartym wierszu wejścia znajduje się ciąg M liczb naturalnych Aj (1 ≤ Aj ≤ 109) pooddzielanych pojedynczymi odstępami. Są to rozmiary obcasów w kolejnych parach klapek w sklepie. W piątym (ostatnim) wierszu wejścia znajduje się jedna liczba naturalna T (1 ≤ T ≤ 2 · 109) – minimalny wzrost, od którego można zjechać ze zjeżdżalni.

출력

W pierwszym (jedynym) wierszu wyjścia należy wypisać jedną nieujemną liczbę całkowitą – największą możliwą liczbę osób, które mogą zjechać ze zjeżdżalni zgodnie z warunkami powyżej.

예제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