Silk Road

Kazakhstan once had a trade route called the Silk Road.

The Silk Road has $N + 1$ cities. From west to east they are city $0$, city $1$, ..., city $N$. The distance between city $i - 1$ and city $i$ ($1 \le i \le N$) is $D_i$.

JOI, a trader, starts at city $0$ and travels through the cities from west to east until reaching city $N$. The trip must finish within $M$ days. Each day JOI picks one of two actions.

• Move: spend the day going to the city immediately to the east. From city $i - 1$ ($1 \le i \le N$), JOI arrives at city $i$.
• Wait: stay in the current city for the day.

Moving builds up fatigue. The weather on day $j$ ($1 \le j \le M$) has badness $C_j$, and moving from city $i - 1$ to city $i$ on day $j$ adds $D_i \times C_j$ fatigue. A day spent waiting adds no fatigue.

Find the smallest total fatigue with which JOI can reach city $N$ within $M$ days.

The first line has two integers $N$ and $M$ ($1 \le N \le M \le 1000$), separated by a space. The Silk Road has $N + 1$ cities, and JOI must get from city $0$ to city $N$ within $M$ days.

Each of the next $N$ lines has one integer. The $i$-th of these lines has $D_i$ ($1 \le D_i \le 1000$), the distance between city $i - 1$ and city $i$.

Each of the next $M$ lines has one integer. The $j$-th of these lines has $C_j$ ($1 \le C_j \le 1000$), the weather badness on day $j$.

Print the smallest total fatigue with which JOI can reach city $N$ within $M$ days, on one line.

In the first example, this schedule reaches the smallest total fatigue.

• Day 1: wait.
• Day 2: move from city $0$ to city $1$. The fatigue added is $10 \times 30 = 300$.
• Day 3: move from city $1$ to city $2$. The fatigue added is $25 \times 15 = 375$.
• Day 4: wait.
• Day 5: move from city $2$ to city $3$. The fatigue added is $15 \times 30 = 450$.

The total fatigue is $300 + 375 + 450 = 1125$, and no schedule does better.