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

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.

입력 형식

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).

출력 형식

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

예제 입력

4 100 200 1
1 4
2 3
3 2
4 0

예제 출력

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.