There is a large amount of packets that need to be delivered within a certain time limit if possible. There are two vehicles available for making the deliveries, a small van and a large lorry.
Each packet is either small or large. A small packet can be delivered either with the van or with the lorry, but a big one requires the lorry. For each packet we know the amount of time it would take to deliver it; we call this the time requirement of the packet. One vehicle can deliver only one packet at a time.
We are also given a deadline, which is the total amount of time within which we should deliver as many packets as possible. We do not care about what happens after the deadline.
Thus, from our point of view, the deliveries take place as follows:
a certain amount of small packets will be delivered
by the van, and the total time requirement of these packets must not exceed
the deadline, and
a certain amount of small and large packets will be delivered by the lorry, and the total time requirement of these packets must also not exceed the deadline.
The task in this problem is to determine the largest total amount of packets that can be delivered in this manner.
The input will be in the file DELIVERY.IN.
The first input line contains a single integer T (1 L T L 1000) - the deadline.
The second input line contains a single integer N (1L NL500) - the total number of small packets.
The input lines 3 through N+2 each contain a single integer between 1 and 1000 (inclusive). These are the time requirements of the small packets. Time requirements are given in ascending order.
The input line number N+3 contains a single integer M (1LML500) - the total number of large packets.
The input lines N+4 through N+M+3 each contain a single integer between 1 and 1000 (inclusive). These are the time requirements of the large packets. These time requirements are also given in ascending order.
The only line of the output file DELIVERY.OUT should contain a single integer - the largest number of packets that can be delivered within the deadline.
Input data(file DELIVERY.IN)
Output data(file DELIVERY.OUT)
The deadline is 10 time units. There are 8 small packets: 5 with time requirement 2 and 3 with time requirement 4. There are 4 large packets: 2 with time requirement 3 and 2 with time requirement 6.
The 8 packets can be delivered in 10 time units by delivering the small packets with time requirement 2 with the van, and using the lorry to deliver one small packet with time requirement 4 and 2 large packets with time requirement 3.