정원 조경

농부 존이 정원을 새로 꾸미려고 한다. 그 과정에서 많은 양의 흙을 옮겨야 한다.

정원은 화단 $N$개가 일렬로 놓인 모양이다 ($1 \le N \le 100\,000$). 처음에 $i$번 화단에는 흙이 $A_i$단위 들어 있다. 존은 작업이 끝났을 때 $i$번 화단에 흙이 정확히 $B_i$단위 있도록 정원을 다시 만들고 싶다. $A_i$와 $B_i$는 모두 $0$ 이상 $10$ 이하의 정수다.

존이 쓸 수 있는 방법은 세 가지다.

1. 흙 $1$단위를 사서 원하는 화단에 넣는다. 비용은 $X$다.
2. 원하는 화단에서 흙 $1$단위를 파내 실어 보낸다. 비용은 $Y$다.
3. 흙 $1$단위를 $i$번 화단에서 $j$번 화단으로 옮긴다. 비용은 $Z \times |i-j|$다.

모든 화단을 목표 상태로 만드는 데 드는 최소 비용을 구하라.

첫째 줄에 $N$, $X$, $Y$, $Z$가 주어진다 ($0 \le X, Y \le 10^8$, $0 \le Z \le 1000$). 이어지는 $N$개의 줄 중 $i$번째 줄에 정수 $A_i$와 $B_i$가 주어진다.

조경을 끝내는 데 드는 최소 비용을 출력한다.

같은 문제가 예전에 훨씬 작은 제한으로 출제된 적이 있다. 이 버전은 제한이 크게 늘어났으므로, 작은 제한을 가정하고 짠 풀이로는 시간 안에 끝내기 어렵다.