There are $N$ pillars arranged in a line on a 2D plane. The pillars are numbered with natural numbers from 1 to $N$ from left to right.

The base of the $i$-th pillar ($1 \le i \le N$) is located at point $(D_i, 0)$, and its height is $H_i$. Thus, this pillar is a line segment connecting $(D_i, 0)$ and $(D_i, H_i)$. Also, $D_1 = 0$.

Initially, the flying squirrel is at height $L$ on the leftmost pillar, i.e., at point $(0, L)$. The flying squirrel wants to go to height $R$ on the rightmost pillar, i.e., at point $(D_N, R)$, by passing through all pillars in order from left to right.

When the flying squirrel flies from one pillar to the next, moving $d$ ($d \ge 0$) units to the right results in a decrease in height by $d$. It must not touch the ground before reaching the next pillar. Reaching the height 0 of the next pillar is allowed.

The flying squirrel can climb up or descend on a pillar. It cannot climb higher than the height of the pillar. Climbing up $h$ ($h \ge 0$) units on the $i$-th pillar costs $W_i \times h$. Descending on a pillar costs nothing.

Figure 1 below shows one example of how the flying squirrel moves.

Figure 1

Moving as shown on the left of Figure 2 is not allowed because it touches the ground in the middle. Moving as shown on the right of Figure 2 is also not allowed because it skips a pillar.

Figure 2

Calculate the minimum total cost for the flying squirrel to reach the target position.

Implementation Details

You must implement the following function:

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

• This function is called exactly once.
• The size of the 3 arrays given as arguments is $N$, the number of pillars.
• $D[i]$ in the integer array $D$ is the distance $D_{i+1}$ from the 1st pillar to the $(i+1)$-th pillar.
• $H[i]$ in the integer array $H$ is the height $H_{i+1}$ of the $(i+1)$-th pillar.
• $W[i]$ in the integer array $W$ is the cost $W_{i+1}$ to climb 1 unit on the $(i+1)$-th pillar.
• $L$ is the initial height of the flying squirrel on the 1st pillar.
• $R$ is the height the flying squirrel must reach on the $N$-th pillar.
• The return value of this function:
  • If there is a way to reach the final position while following the rules, it should be the minimum cost for the flying squirrel to reach the final position. It can be proven that the minimum cost for input data satisfying the constraints is always an integer.
  • If there is no way to reach the final position while following the rules, it should be -1.

Do not execute any input/output functions in any part of the submitted source code.

Constraints

• $2 \le N \le 500\,000$
• $0 = D_1 < D_2 < \dots < D_N \le 10^9$
• $1 \le H_i \le 10^9$ ($1 \le i \le N$)
• $0 \le W_i \le 10^9$ ($1 \le i \le N$)
• $0 \le L \le H_1$
• $0 \le R \le H_N$

Subtasks

1. (4 points) $W_i = 0$ ($1 \le i \le N$)
2. (13 points) $W_i = 1$ ($1 \le i \le N$)
3. (18 points) $W_i \le W_{i+1}$ ($1 \le i \le N - 1$)
4. (15 points) $N \le 500$, $H_i \le 500$ ($1 \le i \le N$)
5. (18 points) $N \le 5\,000$
6. (32 points) No additional constraints.

Note

Note that the score for each subtask is the minimum of the scores for all data in that subtask.

Examples

Consider the case where $N = 3$, the distance from the 1st pillar to the 2nd is 2, the distance from the 1st pillar to the 3rd is 5, the heights of the pillars from left to right are 8, 5, 5, the weights of the pillars from left to right are 3, 4, 6, $L = 5$, and $R = 4$.

The grader calls the following function:

fly({0, 2, 5}, {8, 5, 5}, {3, 4, 6}, 5, 4) = 18

In this case, it is optimal to climb 2 units on the 1st pillar and 2 units on the 3rd pillar, so the function should return 18.

This example satisfies the conditions for subtasks 3, 4, 5, and 6.

Sample grader

The sample grader receives input in the following format:

• Line 1: $N$
• Line $1 + i$ ($1 \le i \le N$): $D_i$ $H_i$ $W_i$
• Line $2 + N$: $L$ $R$

The sample grader outputs the following:

• Line 1: The value returned by the function fly

Note that the sample grader may differ from the grader used in actual evaluation.