Page not loading? Try clicking here.
Placeholder

#3976
Grading on hold

Landscaping 2s 512MB

Problems

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

Problem credits: Brian Dean


Input

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

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


Example 

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.


Source

USACO 2016 US Open Platinum

You must sign in to write code.