Hide

Problem K
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:

  1. Gate $1$ to Gate $2$ (cost $5$)

  2. Gate $2$ to Gate $1$ (cost $5$)

  3. Gate $1$ to Gate $2$ to Gate $3$ (cost $9$)

  4. Go between Gate $3$ and Gate $4$ until $7$-th hour (cost $6$)

  5. 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

Please log in to submit a solution to this problem

Log in