날다람쥐

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

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

문제

제한