Landscaping
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 Ai units of dirt. Farmer John would like to re-landscape the garden so that each flowerbed i instead contains Bi units of dirt. The Ai's and Bi'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.
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
Source: USA Computing Olympiad.
Input Format
The first line of input contains N, X, Y, and Z (0≤X,Y≤108;0≤Z≤1000). Line i+1 contains the integers Ai and Bi.
Output Format
Please print the minimum total cost FJ needs to spend on landscaping.