Problem M
Crazy Driver
In the Linear City, there are $N$ gates arranged in a straight line. The gates are labelled from $1$ to $N$. Between adjacent gates, there is a bidirectional road. Each road takes one hour to travel and has a toll fee. Since the roads are narrow, you can only travel from gates to gates but cannot U-turn between gates.
Crazy driver Gary starts at Gate $1$ at time $0$ and he wants to drive through Gate $N$ while minimizing the cost of travelling. However, Gate $i$ only allows a car to pass through after a certain time $T_ i$. As Gary is crazy, his car will always be traveling on any one of the roads, i.e., it will not stop at a gate. What is the minimum cost for him to drive through Gate $N$?
As an example, consider the sample input below. An optimal solution is the following:
-
Gate $1$ to Gate $2$ (cost $5$)
-
Gate $2$ to Gate $1$ (cost $5$)
-
Gate $1$ to Gate $2$ to Gate $3$ (cost $9$)
-
Go between Gate $3$ and Gate $4$ until $7$-th hour (cost $6$)
-
Go to and pass through Gate $5$ (cost $8$)
Input
The first line contains an integer, $N$ ($2 \leq N \leq 10^5$), the number of gates. The second line has $N-1$ integers, $C_1, \dots , C_{N-1}$. $C_ i$ ($1 \leq C_ i \leq 10^6$) represents the toll fee of the road between Gate $i$ and Gate $i+1$. The third line has $N$ integers, $T_1, \dots , T_ N$. $T_ i$ ($0 \leq T_ i \leq 10^6$) represents the opening time (in hour) for each gate. $T_1$ will always be 0.
Output
Output an integer representing the minimum cost of traveling.
| Sample Input 1 | Sample Output 1 |
|---|---|
5 5 4 2 8 0 2 4 4 8 |
33 |
