Car factory
Time Limit : 3000/1000ms (Java/Other) Memory Limit : 65535/32768K (Java/Other)
Total Submission(s) : 0 Accepted Submission(s) : 0
Font: Times New Roman | Verdana | Georgia
Font Size: ← →
Problem Description
As mentioned before, there are N workers in Mirko’s factory. They are manufacturing cars on a conveyor belt, in a pipeline fashion. Workers are denoted by numbers 1 – leftmost, to N - rightmost.
Each of the workers does his specific job and requires certain amount of time to complete it.
Production of a single car starts with worker #1 (Mirko). After he had finished with his part of the job, worker #2 takes over, after him #3... When worker #N finishes with his part, the car is finished. Mirko and his workers have to produce M cars and they must produce them in order 1 to M.
For every worker i we know Ti - time required for him to do his part of the job. For every car j we know factor of assembly complexity Fj. Time in minutes for worker i to finish his part of he job on the car j is computed as a product TiFj.
After some worker has finished working on a car, he has to give it to the next worker instantly, without any delay (weird company policy). For that reason, the worker receiving the car has to be free (he must not be working on some other car). In order to fulfill this condition, Mirko has to choose a good timing to start building a new car. To be efficient, he’ll wait minimum number of minutes until he is certain that all of the conditions described are met.
Write a program which will given worker times and factors of complexity for each car, compute total time required for producing all of the cars.
Each of the workers does his specific job and requires certain amount of time to complete it.
Production of a single car starts with worker #1 (Mirko). After he had finished with his part of the job, worker #2 takes over, after him #3... When worker #N finishes with his part, the car is finished. Mirko and his workers have to produce M cars and they must produce them in order 1 to M.
For every worker i we know Ti - time required for him to do his part of the job. For every car j we know factor of assembly complexity Fj. Time in minutes for worker i to finish his part of he job on the car j is computed as a product TiFj.
After some worker has finished working on a car, he has to give it to the next worker instantly, without any delay (weird company policy). For that reason, the worker receiving the car has to be free (he must not be working on some other car). In order to fulfill this condition, Mirko has to choose a good timing to start building a new car. To be efficient, he’ll wait minimum number of minutes until he is certain that all of the conditions described are met.
Write a program which will given worker times and factors of complexity for each car, compute total time required for producing all of the cars.
Input
The input consists of multiple test cases.First line of input contains space-separated positive integers N (1 ≤ N ≤ 100 000), number of workers, and M (1 ≤ M ≤ 100 000), number of cars. In test cases worth 40% of total data, N and M will be at most 1000.
i-th of the following N lines contains worker time Ti for the worker i.
j-th of the following M lines contains factor of complexity Fj for the car j.
These conditions hold: 1 ≤ Ti ≤ 10 000, 1 ≤ Fj ≤ 10 000.
i-th of the following N lines contains worker time Ti for the worker i.
j-th of the following M lines contains factor of complexity Fj for the car j.
These conditions hold: 1 ≤ Ti ≤ 10 000, 1 ≤ Fj ≤ 10 000.
Output
First and only line of output has to contain required number of minutes.
Sample Input
3 3 2 1 1 2 1 1 3 3 2 3 3 2 1 2 4 5 3 2 2 2 3 1 2 1 2
Sample Output
11 29 55
Source
2012暑假集训