P9749 [CSP-J 2023] Highway

Xiaobao plans to drive along a highway for a road trip. There are a total of $n$ stations on the highway, numbered from $1$ to $n$. The distance between station $i$ and station $i + 1$ is $v_i$ kilometers. At every station, you can refuel. At station $i$, the price per liter is $a_i$ yuan, and each station sells only an integer number of liters. Xiaobao wants to drive from station $1$ to station $n$. At the beginning, Xiaobao is at station $1$ and the fuel tank is empty. It is known that the fuel tank is large enough to hold any amount of fuel, and each liter of fuel allows the car to travel $d$ kilometers. Find the minimum cost of refueling needed for Xiaobao to drive from station $1$ to station $n$.

The first line contains two positive integers $n$ and $d$, representing the number of stations on the highway and the distance the car can travel per liter of fuel. The second line contains $n - 1$ positive integers $v_1, v_2\dots v_{n-1}$, representing the distances between adjacent stations. The third line contains $n$ positive integers $a_1, a_2 \dots a_n$, representing the refueling price at each station.

Output one line containing only one positive integer, representing the minimum money Xiaobao needs to spend on refueling to drive from station $1$ to station $n$.

**[Sample 1 Explanation]** In the optimal plan: Xiaobao buys $3$ liters at station $1$, buys $5$ liters at station $2$, and buys $2$ liters at station $4$. **[Sample 2]** See `road/road2.in` and `road/road2.ans` under the contestant directory. **[Constraints]** For all testdata, it is guaranteed that: $1 \leq n \leq 10^5$, $1 \leq d \leq 10^5$, $1 \leq v_i \leq 10^5$, $1 \leq a_i \leq 10^5$. ::cute-table{tuack} | Test Point | $n \leq$ | Special Property | | :----------: | :----------: | :----------: | | $1\sim 5$ | $8$ | None | | $6\sim 10$ | $10^3$ | ^ | | $11\sim 13$ | $10^5$ | A | | $14\sim 16$ | ^ | B | | $17\sim 20$ | ^ | None | - Special Property A: Station $1$ has the lowest fuel price. - Special Property B: For all $1 \leq i < n$, $v_i$ is a multiple of $d$. Translated by ChatGPT 5