Under construction

Still being built. Things may change

High-Heeled Flip-Flops

Interview

Time limit2sMemory limit1024 MB

Summary
Given people's heights and flip-flop heel heights, find the maximum number of people who can reach height T, with each person wearing at most one pair.
Level

Medium5 of 10

Topics
Greedy, Sorting, Two pointers
Solved
No attempts yet

Problem

A new waterslide has opened at the aquapark in Bajtocja. Unfortunately, only people who are at least TT bytometers tall may ride it.

The shop next to the aquapark sells special heeled flip-flops. Putting on the jj-th pair makes the wearer AjA_j bytometers taller. Nobody asks people to take their flip-flops off when their height is measured. Each person may wear at most one pair.

Bajtek and his friends want to plan which flip-flops to buy and who wears which pair, so that as many people as possible can ride the slide. For hygiene reasons, people cannot swap flip-flops after putting them on.

Write a program that finds the largest number of people who can ride the slide under an optimal plan for the flip-flops.

Input

The first line contains a natural number NN (1≤N≤2000001 \le N \le 200000), the number of people in the group, including Bajtek. The second line contains NN natural numbers HiH_i (1≤Hi≤1091 \le H_i \le 10^9) separated by single spaces, the heights of the people in the group. The third line contains a non-negative integer MM (0≤M≤2000000 \le M \le 200000), the number of pairs of flip-flops in the shop. The fourth line contains MM natural numbers AjA_j (1≤Aj≤1091 \le A_j \le 10^9) separated by single spaces, the heel heights of the pairs in the shop. The fifth (last) line contains a natural number TT (1≤T≤2⋅1091 \le T \le 2 \cdot 10^9), the minimum height required to ride the slide.

Output

The only line of output contains one non-negative integer, the largest possible number of people who can ride the slide under the conditions above.

Examples2

  1. Example 1

    Input
    5
    5 15 10 12 1
    3
    12 2 1
    14
    
    Expected output
    3
    
  2. Example 2

    Input
    5
    7 3 2 5 1
    0
    
    3
    
    Expected output
    3