P3399 Silk Road

In 138 BCE, Zhang Qian braved great hardships to serve as an envoy to the Western Regions, strengthening friendly exchanges between the Han dynasty and various states there. Since then, caravans of camels have traveled along this long trade route. They crossed lofty mountains, bringing China’s advanced technologies to Central Asia, West Asia, and Europe, and brought spices and fine horses from those regions into China. Whenever people gaze upon the desolate desert with a solitary plume of smoke, it evokes imagination of the past prosperity of trade and culture.

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.

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 a single integer, the minimal total fatigue.

### 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