Pipe Cutting
InterviewTime limit2sMemory limit128 MB
Given M long pipes and N required short pipe lengths, compute the maximum number of short pipes that can be cut from the long pipes.
Problem
A construction company needs N short steel pipes for a new building. The company already has M leftover long steel pipes from previous work, and it wants to cut those first before ordering any additional pipes.
One long pipe may be cut multiple times to produce several short pipes. Ignore any length lost during cutting. Find the maximum number of required pipes that can be produced from the given long pipes.
Input
The first line contains the number M of long steel pipes. (1 <= M <= 50)
The second line contains the lengths of the M long steel pipes. Each length is a positive integer not greater than 100,000.
The third line contains the number N of required short pipes. (1 <= N <= 1023)
The fourth line contains N integers, the lengths of the pipes to be made. Each length is a natural number not greater than 128.
Output
Print the maximum number of required pipes that can be produced.