Mirko's Assembly Line Scheduling

Mirko's factory has n workers arranged in a production line (from worker 1 to worker n), where worker 1 (Mirko himself) starts the manufacturing of a car. After a worker finishes his assigned part, he must immediately hand over to the next worker, without any delay. When worker n finishes his work, one car is completed.

The factory needs to produce m cars in order (from car 1 to car m). The time taken by worker i to finish his work is t_i. For the j-th car, the assembly complexity is f_j, so the time worker i takes on car j is t_i \cdot f_j.

To ensure the handover is immediate and there is no delay, Mirko must choose the starting times for each car carefully. The minimal total production time can be computed using the following recurrence:

\[ F_{i,j} = \max(F_{i-1,j},\,F_{i,j-1}) + t_i \cdot f_j \]

with the base cases:

\[ \begin{aligned} F_{1,1} &= t_1 \cdot f_1,\\ F_{1,j} &= F_{1,j-1} + t_1 \cdot f_j,\\ F_{i,1} &= F_{i-1,1} + t_i \cdot f_1. \end{aligned} \]

Your task is to compute the minimum total time needed to produce all m cars.

inputFormat

The first line contains two integers n and m, representing the number of workers and the number of cars respectively.

The second line contains n integers: t₁, t₂, ..., t_n, where t_i is the time taken by worker i.

The third line contains m integers: f₁, f₂, ..., f_m, where f_j is the complexity of car j.

outputFormat

Output a single integer: the total minimum time required to produce all m cars.

sample

3 2
1 2 3
2 2

18