Problem Description

Mirko's factory has \( n \) workers who manufacture cars on an assembly line. The workers are numbered from 1 to \( n \) from left to right, with worker 1 being Mirko. The car production starts with worker 1 (Mirko), and after he completes his tasks, worker 2 takes over. This process continues sequentially until worker \( n \) completes his tasks, at which point a car is finished.

Mirko and his workers need to produce \( m \) cars in order from 1 to \( m \). For the \( i \)-th worker, the time it takes to complete his tasks is \( t_i \). For the \( j \)-th car, the assembly complexity is \( f_j \). The time required for worker \( i \) to complete his tasks on car \( j \) is \( t_i \cdot f_j \).

According to company policy, a worker must immediately pass on his work to the next worker without delay. Therefore, the next worker cannot be working on another car at that time. To meet this condition, Mirko must wait for the optimal moment to start manufacturing a new car to minimize the waiting time while ensuring all conditions are met.

Write a program that, given the time each worker takes to complete his tasks and the assembly complexity of each car, calculates the total time required to produce all cars.

Input Format

The input consists of \( n+m+2 \) lines.

• The first line contains two integers \( n \) and \( m \), representing the number of workers and the number of cars to be produced, respectively.
• The next \( n \) lines each contain an integer \( t_i \), indicating the time it takes for the \( i \)-th worker to complete his tasks.
• The following \( m \) lines each contain an integer \( f_j \), indicating the assembly complexity of the \( j \)-th car.

Output Format

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

Sample Input and Output

Input Sample #1

3 3
2
1
1
2
1
1

Output Sample #1

11

Input Sample #2

3 3
2
3
3
2
1
2

Output Sample #2

29

Input Sample #3

4 5
3
2
2
2
3
1
2
1
2

Output Sample #3

55

Notes

[Sample 1 Explanation]

For Sample 1, after 4 units of time, worker 1 completes the work on the first car. He might immediately start working on the second car, but this would violate the condition that the car must be passed on immediately to the next worker (after 7 units of time, the second worker would complete his work on the second car, but the third worker 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. Thus, the total time is 11.

[Data Range]

For 40% of the data, \( n, m \leq 1000 \).
For all data, \( 1 \leq n, m \leq 10^5 \), \( 1 \leq t_i, f_j \leq 10^4 \).

[Problem Source]

This problem is from COCI 2011-2012 CONTEST 3 T6 TRAKA, configured with the original data, with a full score of 160 points.

Provided by Eason_AC for translation and arrangement.

见题面 Input 部分

见题面 Output 部分