Description

A little hamster is delivering goods from China to Baghdad. The Silk Road has $N+1$ cities including the start and the end. City $0$ is the starting point Chang’an, and city $N$ is the destination Baghdad. The hamster must reach the destination in at most $M$ days. In one day, it is possible to travel from one city to the next consecutive city. The distance from city $i-1$ to city $i$ is $D_i$.

As everyone knows, traveling continuously is exhausting, so when staying in a city, the hamster has two choices:

• Move: set off toward the next city.
• Rest: stay in the current city without moving.

Desert weather is unpredictable. When the weather is bad, moving forward is much more difficult. Let the severity of the weather on the $j$-th day ($1 \le j \le M$) be $C_j$. If the hamster moves from city $i-1$ to city $i$ on day $j$, it incurs a fatigue of $D_i \times C_j$.

However, the hamster can choose to avoid worse weather; resting consumes no fatigue. Now it wants to know the minimum total fatigue for the whole trip.

Input Format

The first line contains $2$ integers $N$ and $M$.

The next $N$ lines each contain one integer $D_j$.

The next $M$ lines each contain one integer $C_j$.

Output Format

Output a single integer, the minimal total fatigue.

3 5
10
25
15
50
30
15
40
30

1125

Hint

Sample Explanation

Rest on day $1$.

On day $2$, $0 \rightarrow 1$, fatigue $10 \times 30 = 300$.

On day $3$, $1 \rightarrow 2$, fatigue $25 \times 15 = 375$.

Rest on day $4$.

On day $5$, $2 \rightarrow 3$, fatigue $15 \times 30 = 450$.

Constraints

$1 \le N \le M \le 1000$.

$1 \le D_i, C_i \le 1000$.

Translated by ChatGPT 5