IOI '96 - Veszprém, Hungary
A factory is running a production line. Two operations have to be
performed on each job: first operation A
, then operation B
. There is
a certain number of machines capable of performing each operation.
The figure above shows the organisation of the production line that
works as follows. A type A
machine takes a job from the input
container, performs operation A
and puts the job into the intermediate
container. A type B
machine takes a job from the intermediate
container, performs operation B
and puts the job into the output
container. All machines can work in parallel and independently of each
other, and the size of each container is unlimited. The machines have
different performance characteristics, a given machine works with a
given processing time.
Give the earliest time operation A
can be completed for all jobs
provided that the jobs are available at time . Compute the minimal
amount of time that is necessary to perform both operations
(successively, of course) on all jobs.
Input Specification
- Line 1: One integer , the number of jobs .
- Line 2: One integer , the number of type
A
machines. - Line 3: integers, the job processing times of each type
A
machine. - Line 4: One integer , the number of type
B
machines. - Line 5: integers, the job processing times of each type
B
machine.
The job processing time is measured in units of time, which includes the time needed for taking a job from a container before processing and putting it into a container after processing. Each processing time is at least and at most .
Output Specification
Your program should output two integers on separate lines. The first
line should contain the minimum time to perform all A
tasks, and the
second should contain the minimum time to perform all B
tasks (which
require A
tasks, of course).
Sample Input
5
2
1 1
3
3 1 4
Sample Output
3
5
Comments