Flying Squirrel Over Pillars

In a two‐dimensional plane, there are N pillars arranged in order from left to right and numbered from 1 to N. The base of the i-th pillar is at the point \( (D_i,0) \) and its top is at \( (D_i, H_i) \), meaning the pillar is a line segment between \( (D_i,0) \) and \( (D_i,H_i) \). It is given that \( D_1=0 \).

Initially, a flying squirrel is at height L on the first pillar, i.e. at the point \( (0,L) \). The squirrel must visit every pillar in order and finally reach height R on the last pillar, i.e. at \( (D_N,R) \).

When the squirrel flies from one pillar to the next (say from pillar \(i\) to pillar \(i+1\)), the horizontal displacement is \( d = D_{i+1} - D_i \) (\( d \ge 0 \)) and the squirrel loses exactly \( d \) units of height during the flight. The squirrel must not touch the ground (height 0) during the flight; however, arriving at the next pillar exactly at height 0 is permitted.

On a pillar, the squirrel can adjust its height by climbing up or sliding down. Climbing up by \( h \) units (\( h\ge 0 \)) on the i-th pillar costs \( W_i \times h \) and the squirrel cannot climb above the pillar’s top (i.e. above \( H_i \)). Sliding downward is free. Note that the adjustments on the pillar are made before initiating the flight to the next pillar. In other words, if the squirrel is at height \( h \) on pillar \( i \) and chooses to adjust to height \( x \) (where \( 0 \le x \le H_i \)), the cost incurred on pillar \( i \) is \[ \text{cost} = W_i \times \max(0,\, x - h), \] and when flying, the squirrel’s height decreases by \( d \), landing at height \( x-d \) on pillar \( i+1 \). For the flight to be valid, it must be that \( x-d \ge 0 \) (so the squirrel does not hit the ground mid-flight) and after landing the height must not exceed the top of pillar \( i+1 \), i.e. \( x-d \le H_{i+1} \).

The squirrel is allowed to further adjust its height on the final (\( N \)th) pillar to exactly \( R \) (again with the climbing cost if climbing up, or sliding down for free). Your task is to compute the minimum total cost required for the squirrel to reach the target position \( (D_N,R) \) by following the rules. If it is impossible to complete the journey, output -1.

You need to implement the function

long long fly(vector<int> D, vector<int> H, vector<int> W, int L, int R);

The arrays D, H, and W are of length N, where for \( 1 \le i \le N \), \( D[i-1] \) represents \( D_i \) (with \( D_1=0 \)), \( H[i-1] \) represents \( H_i \), and \( W[i-1] \) represents \( W_i \). The integers L and R denote the starting and target heights on the first and last pillars respectively.

If there exists a sequence of moves following the rules that leads the squirrel to \( (D_N,R) \), return the minimum total cost (which is guaranteed to be an integer for valid inputs). Otherwise, return -1.

inputFormat

The input is given in the following format:

N
D[0] D[1] ... D[N-1]
H[0] H[1] ... H[N-1]
W[0] W[1] ... W[N-1]
L R

Note: It is guaranteed that \( D[0]=0 \).

outputFormat

Output a single integer which is the minimum total cost to reach the target position. If it is impossible, output -1.

sample

3
0 2 5
3 3 10
1 1 2
2 5

13