Landscaping

Farmer John is rebuilding his garden, and the work involves moving a large amount of dirt.

The garden is a row of $N$ flowerbeds ($1 \le N \le 100\,000$). Flowerbed $i$ starts with $A_i$ units of dirt. Farmer John wants flowerbed $i$ to hold exactly $B_i$ units of dirt once the work is done. Every $A_i$ and every $B_i$ is an integer between $0$ and $10$.

Farmer John has three moves.

1. Buy one unit of dirt and place it in any flowerbed, at a cost of $X$.
2. Remove one unit of dirt from any flowerbed and have it shipped away, at a cost of $Y$.
3. Transport one unit of dirt from flowerbed $i$ to flowerbed $j$, at a cost of $Z \times |i-j|$.

Compute the minimum total cost of bringing every flowerbed to its target state.

The first line contains $N$, $X$, $Y$, and $Z$ ($0 \le X, Y \le 10^8$, $0 \le Z \le 1000$). Line $i+1$ contains the integers $A_i$ and $B_i$.

Print the minimum total cost of the landscaping work.

The same task appeared earlier with much smaller limits. This version raises them considerably, so a solution written for the easier version will not finish in time.