Description

There are $n$ workers in Mirko’s factory. They manufacture cars on a conveyor belt in an assembly-line manner. The workers are numbered from left to right as $1 \sim n$, and worker $1$ is Mirko. The production of a car starts with worker $1$ (Mirko). After he finishes all his work, worker $2$ takes over. Then worker $3$ takes over worker $2$’s work, and so on. When worker $n$ finishes his work, the car is completed.

Mirko and his workers must produce $m$ cars, and they must be produced in order from $1 \sim m$. For worker $i$, the time needed to complete his part is $t_i$. For car $j$, its assembly complexity is $f_j$. The time worker $i$ needs to finish his work on car $j$ is $t_i \cdot f_j$.

According to company policy, after a worker finishes his work, he must immediately pass the work to the next worker without any delay. Therefore, at that moment, the next worker must not be working on another car. To satisfy this condition, Mirko must wait for a suitable moment to start making a new car. To improve efficiency, he will wait the minimum amount of time until he is sure that all conditions can be satisfied.

Write a program that, given the time needed for each worker to complete his work and the assembly complexity of each car, computes the total time required to produce all cars.

Input Format

The input contains a total of $n + m + 2$ lines.

The first line contains two integers $n, m$, representing the number of workers and the number of cars to be produced.
The next $n$ lines each contain one integer $t_i$, denoting the time needed for worker $i$ to complete his work.
The next $m$ lines each contain one integer $f_j$, denoting the assembly complexity of car $j$.

Output Format

Output a single line containing one integer, representing the total time required to produce all cars.

3 3
2
1
1
2
1
1

11

3 3
2
3
3
2
1
2

29

4 5
3
2
2
2
3
1
2
1
2

55

Hint

[Sample 1 Explanation]

For sample $1$, after $4$ units of time, worker $1$ finishes his work on the first car. He could immediately start working on the second car, but that would violate the condition that a car must be passed to the next worker immediately after it is finished (after $7$ units of time, worker $2$ would finish his work on the second car, but worker $3$ cannot take over because he is still working on the first car). Therefore, the second car can only start production after $5$ units of time. The third car starts production after $7$ units of time. The first car is completed after $8$ units of time, the second car after $9$ units of time, and the third car after $11$ units of time. Therefore, the total time is $11$.

[Constraints]

For $40\%$ of the testdata, $n, m \leqslant 1000$.
For all testdata, $1 \leqslant n, m \leqslant 10^5$, and $1 \leqslant t_i, f_j \leqslant 10^4$.

[Source]

This problem comes from COCI 2011-2012 CONTEST 3 T6 TRAKA, using the original testdata configuration, with a full score of $160$ points.

Translated and organized by Eason_AC.

Translated by ChatGPT 5