7907: USACO 2016 US Open Contest, Platinum —— Problem 3. Landscaping
[Creator : ]
Description
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≤N≤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…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.
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
The first line of input contains $N, X, Y, Z\ (0≤X,Y≤10^8;\ 0≤Z≤1000)$.
Line $i+1$ contains the integers $A_i$ and $B_i$.
Line $i+1$ contains the integers $A_i$ and $B_i$.
Output
Please print the minimum total cost FJ needs to spend on landscaping.
Sample 1 Input
4 100 200 1
1 4
2 3
3 2
4 0
Sample 1 Output
210