High-Heeled Flip-Flops
InterviewTime limit2sMemory limit1024 MB
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 bytometers tall may ride it.
The shop next to the aquapark sells special heeled flip-flops. Putting on the -th pair makes the wearer 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 (), the number of people in the group, including Bajtek. The second line contains natural numbers () separated by single spaces, the heights of the people in the group. The third line contains a non-negative integer (), the number of pairs of flip-flops in the shop. The fourth line contains natural numbers () separated by single spaces, the heel heights of the pairs in the shop. The fifth (last) line contains a natural number (), 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.