Flying Squirrel

There are $N$ pillars in a row on a two-dimensional plane. The pillars are numbered from 1 to $N$ from left to right.

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

At the start, the flying squirrel is at height $L$ on the leftmost pillar, that is, at the point $(0, L)$. The squirrel wants to pass through all pillars in order from left to right and reach height $R$ on the rightmost pillar, that is, the point $(D_N, R)$.

When the squirrel flies from one pillar to the next, if it moves $d$ ($d \ge 0$) to the right, its height decreases by $d$. It must not touch the ground before it reaches the next pillar. Arriving at height 0 on the next pillar is allowed.

On a pillar, the squirrel can climb up or move down. It cannot climb above the height of the pillar. Climbing up by $h$ ($h \ge 0$) on the $i$-th pillar costs $W_i \times h$. Moving down costs nothing.

Figure 1 shows one possible route of the squirrel.

Figure 1

The route on the left of Figure 2 is not allowed, because the squirrel touches the ground along the way. The route on the right of Figure 2 is also not allowed, because it skips some of the pillars.

Figure 2

Compute the minimum total cost for the squirrel to reach the target position.

• $2 \le N \le 500000$
• $0 = D_1 < D_2 < \cdots < 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$