Riyuna Likes Sailor Uniforms
InterviewTime limit1sMemory limit256 MB
Given N shirt widths and M collar widths, a collar of width c fits a shirt of width w if w/2 <= c <= 3w/4 or w <= c <= 5w/4; find the maximum number of valid shirt-collar pairs.
- Level
Medium5 of 10
- Topics
- Greedy, Two pointers, Sorting, Intervals
- Solved
- No attempts yet
Problem
Riyuna really likes sailor uniforms. So she plans to make a great many sailor uniforms and put them on other people as well.
Making a sailor uniform requires two materials: a white T-shirt and a sailor collar. The way to make a sailor uniform from the two is as follows.
Figure 1: The process of making a sailor uniform
Riyuna wanted to turn every white T-shirt in the world into a sailor uniform, but a lack of budget and time meant she could only get N white T-shirts. She also had to make many sailor collars, but for the same reason she managed to make only M of them.
On top of that, she made the sailor collars in too much of a hurry, so their sizes came out uneven. Not just any sailor collar can be attached to any T-shirt. When the width of a white T-shirt is an integer w, there are two kinds of sailor collar that can be attached to it. A sailor collar whose width is at least w/2 and at most w×3/4 can be attached, or, because the collar is made slightly wider than the shirt, a collar whose width is at least w and at most w×5/4 can be attached. Any other case Riyuna does not like, so she will not make it.
Even under these conditions, Riyuna wants to make as many sailor uniforms as possible. Tell her the maximum number of sailor uniforms she can make.
Input
The first line gives the numbers of white T-shirts and sailor collars she has. (1 ≤ N, M ≤ 200)
From the second line, N lines give the width w of each white T-shirt. (1 ≤ w ≤ 1,000)
From the N+2-th line, M lines give the width w of each sailor collar. (1 ≤ w ≤ 1,000)
The width w is an integer in both cases.
Output
Print the maximum number of sailor uniforms that can be made on the first line.