Problem Description

There was an ancient trade route called the "Silk Road" in the region where Kazakhstan is now located.

The Silk Road has $ N + 1 $ cities numbered from west to east as city $ 0 $, city $ 1 $, $\ldots$, city $ N $. The distance between city $ i - 1 $ and city $ i $ ($1 \leq i \leq N$) is $ D_i $.

JOI, a merchant, has to transport silk from city $ 0 $ to city $ N $ by visiting the cities in order. He must complete this journey within $ M $ days. JOI can choose one of the following two actions each day:

• Move: Spend one day moving from the current city to the next eastern city. If he is in city $ i - 1 $ ($1 \leq i \leq N$), he moves to city $ i $.
• Wait: Stay in the current city for one day without moving.

Moving is strenuous, and fatigue accumulates with each move. The Silk Road experiences daily fluctuations in weather, and bad weather makes moving more difficult.

It is known that the harshness of the weather on the $ j $th day ($1 \leq j \leq M$) is $ C_j $. If JOI moves from city $ i - 1 $ to city $ i $ on the $ j $th day ($1 \leq i \leq N$), he accumulates $D_i \times C_j$ fatigue. Waiting does not accumulate fatigue.

JOI wants to minimize the total fatigue accumulated during his journey within $ M $ days. Calculate the minimum total fatigue JOI accumulates when moving from city $ 0 $ to city $ N $.

Input Format

The input consists of $ 1 + N + M $ lines.

The first line contains two integers $ N, M $ ($1 \leq N \leq M \leq 1,000$), indicating that the Silk Road consists of $ N + 1 $ cities and JOI must transport silk from city $ 0 $ to city $ N $ within $ M $ days.

The next $ N $ lines contain an integer $ D_i $ ($1 \leq D_i \leq 1,000$), representing the distance between city $ i - 1 $ and city $ i $.

The next $ M $ lines contain an integer $ C_j $ ($1 \leq C_j \leq 1,000$), representing the harshness of the weather on the $ j $th day.

Output Format

Output the minimum total fatigue JOI accumulates when moving from city $ 0 $ to city $ N $ within $ M $ days.

Sample Input and Output

Sample Input #1

3 5
10
25
15
50
30
15
40
30

Sample Output #1

1125

Sample Input #2

2 6
99
20
490
612
515
131
931
1000

Sample Output #2

31589

Notes/Hints

Sample Explanation 1

In sample input #1, JOI can minimize fatigue by:
- Waiting on day 1.
- Moving from city 0 to city 1 on day 2, accumulating $10 \times 30 = 300$ fatigue.
- Moving from city 1 to city 2 on day 3, accumulating $25 \times 15 = 375$ fatigue.
- Waiting on day 4.
- Moving from city 2 to city 3 on day 5, accumulating $15 \times 30 = 450$ fatigue.

The total fatigue accumulated is $ 300 + 375 + 450 = 1,125 $, which is the minimum possible.

见题面 Input 部分

见题面 Output 部分