날다람쥐

2차원 평면 위에 $N$개의 기둥이 일렬로 놓여 있다. 기둥에는 왼쪽에서 오른쪽으로 1번부터 $N$번까지 자연수 번호가 붙어 있다.

$i$ ($1 \le i \le N$)번째 기둥의 바닥은 점 $(D_i, 0)$에 있고, 높이는 $H_i$이다. 따라서 이 기둥은 점 $(D_i, 0)$과 $(D_i, H_i)$를 잇는 선분이다. 또한 $D_1 = 0$이다.

처음에 날다람쥐는 가장 왼쪽 기둥의 높이 $L$인 곳, 즉 점 $(0, L)$에 있다. 날다람쥐는 모든 기둥을 왼쪽부터 순서대로 거쳐서 가장 오른쪽 기둥의 높이 $R$인 곳, 즉 점 $(D_N, R)$에 도착하려고 한다.

날다람쥐가 한 기둥에서 다음 기둥으로 날아갈 때 오른쪽으로 $d$ ($d \ge 0$)만큼 움직이면 높이는 $d$만큼 줄어든다. 다음 기둥에 도착하기 전에 땅에 닿으면 안 된다. 다음 기둥의 높이 0인 곳에 도착하는 것은 허용된다.

날다람쥐는 한 기둥에서 위로 기어오르거나 아래로 내려갈 수 있다. 기둥의 높이보다 더 높은 곳으로 오를 수는 없다. $i$번째 기둥에서 위로 $h$ ($h \ge 0$)만큼 오르면 $W_i \times h$의 비용이 든다. 아래로 내려갈 때는 비용이 들지 않는다.

그림 1은 날다람쥐가 이동하는 한 가지 예이다.

그림 1

그림 2의 왼쪽처럼 이동하면 중간에 땅에 닿으므로 허용되지 않는다. 그림 2의 오른쪽처럼 이동하면 기둥을 거치지 않는 경우가 있으므로 역시 허용되지 않는다.

그림 2

가장 작은 총 비용으로 날다람쥐가 목표 위치에 도착할 수 있는 방법을 계산하라.

• $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$