Conveyor Belt

Time limit1sMemory limit128 MB

Summary

Given worker base times and car complexities on a pipelined assembly line, compute the minimum total completion time respecting sequential handoff constraints.

Level: Medium6 of 10
Topics: Dynamic programming, Greedy, Simulation
Solved: No attempts yet

Problem

A car factory has N workers arranged in a line. The workers are numbered from 1 to N from left to right, and every worker performs a different task.

Each car is completed by passing through worker 1, then worker 2, and so on through worker N. The cars must be produced in order from car 1 to car M. Worker i has base work time T_i, and car j has complexity F_j, so worker i needs T_i * F_j time to finish their task on car j.

When a worker finishes their task, the car is passed immediately to the next worker. At that moment, the next worker must not be busy with another car. Therefore, worker 1 may need to wait before starting a car so that every handoff happens only when the next worker is free.

Given all worker times and car complexities, compute the minimum total time needed to finish all cars.

Input

The first line contains N and M. (1 ≤ N, M ≤ 100,000)

Each of the next N lines contains worker i's base work time T_i. (1 ≤ T_i ≤ 10,000)

Each of the next M lines contains car j's complexity F_j. (1 ≤ F_j ≤ 10,000)

Output

Print one integer: the minimum time needed to finish all cars.

Examples3

Example 1
Input
```
3 3
2
1
1
2
1
1
```
Expected output
```
11
```
Example 2
Input
```
3 3
2
3
3
2
1
2
```
Expected output
```
29
```
Example 3
Input
```
4 5
3
2
2
2
3
1
2
1
2
```
Expected output
```
55
```