Minimum Fatigue Journey

A little hamster is tasked with delivering cargo from China to Anxi along the Silk Road, which consists of \(N+1\) cities. The journey starts at city \(0\) (Chang'an) and ends at city \(N\) (Baghdad). The hamster must reach the destination within at most \(M\) days. In one day, the hamster can move from one city to its immediate next city. The distance from city \(i-1\) to city \(i\) is given by \(D_i\).

However, moving continuously can be exhausting. Thus, while staying in a city, the hamster has two options:

• Move: Advance to the next city.
• Rest: Stay in the current city.

The weather in the desert can change very quickly. For the \(j\)-th day (\(1 \le j \le M\)), the weather adversity is represented by \(C_j\). If the hamster departs on the \(j\)-th day from city \(i-1\) to city \(i\), it will incur a fatigue cost of \(D_i \times C_j\). Resting incurs no fatigue.

The hamster wishes to complete the journey with the minimum possible fatigue. Note that the hamster must perform exactly \(N\) moves (to travel through all \(N\) segments) within \(M\) days (allowing for some rest days). The order of moves must be preserved, meaning if the hamster moves on days \(j_1, j_2, \dots, j_N\), then \(j_1 < j_2 < \cdots < j_N\).

Your task is to compute the minimum total fatigue that the hamster will incur.

Hint: A dynamic programming approach can be employed to decide on which days to move in order to minimize the fatigue cost.

inputFormat

The input consists of three lines:

• The first line contains two integers \(N\) and \(M\) \( (1 \leq N \leq M)\): the number of moves (segments) and the total number of days available.
• The second line contains \(N\) integers: \(D_1, D_2, \dots, D_N\), where \(D_i\) is the distance between city \(i-1\) and city \(i\).
• The third line contains \(M\) integers: \(C_1, C_2, \dots, C_M\), where \(C_j\) is the adversity value for the \(j\)-th day.

outputFormat

Output a single integer representing the minimum total fatigue incurred to complete the journey.

sample

2 3
5 2
3 2 4

18