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, 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.
Input
The first line contains n (1 ≤ n ≤ 10^5), x, y and z (0 ≤ x, y ≤ 10^8, 0 ≤ z ≤ 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.