Farmer John is building a nicely-landscaped garden, and needs to move a large
amount of dirt in the process.

The garden consists of a sequence of $N$ flowerbeds ($1 \leq N \leq 100,000$),
where flowerbed $i$ initially contains $A_i$ units of dirt. Farmer John would
like to re-landscape the garden so that each flowerbed $i$ instead contains
$B_i$ units of dirt. The $A_i$'s and $B_i$'s are all integers in the range
$0 \ldots 10$.

To landscape the garden, Farmer John has several options: he can purchase one
unit of dirt and place it in a flowerbed of his choice for $X$ units of money.
He can remove one unit of dirt from a flowerbed of his choice and have it
shipped away for $Y$ units of money. He can also transport one unit of dirt
from flowerbed $i$ to flowerbed $j$ at a cost of $Z$ times $|i-j|$. Please
compute the minimum total cost for Farmer John to complete his landscaping
project.

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

OUTPUT FORMAT:
Please print the minimum total cost FJ needs to spend on landscaping.

SAMPLE INPUT:
4 100 200 1
1 4
2 3
3 2
4 0
SAMPLE OUTPUT:
210

Note that this problem has been asked in a previous USACO contest,
at the silver level; however, the limits in the present version have
been raised considerably, so one should not expect many points from
the solution to the previous, easier version.

Problem credits: Brian Dean

见题面

见题面