Landscaping#10579
Farmer John is building a beautifully landscaped garden and needs to move a large amount of dirt in the process.
The garden consists of a sequence of flowerbeds, where flowerbed initially contains a_i units of dirt. Farmer John wants to re-landscape the garden so that flowerbed contains exactly b_i units of dirt. All a_i and b_i are integers in the range .
To landscape the garden, Farmer John has several options. He can purchase one unit of dirt and place it in any flowerbed at a cost of units of money. He can remove one unit of dirt from any flowerbed and have it shipped away at a cost of units of money. Alternatively, he can transport one unit of dirt from flowerbed to flowerbed at a cost of z \cdot |i - j|.
Please compute the minimum total cost required for Farmer John to complete his landscaping project.
The first line contains four integers n, x, y, and z~(1 \le n \le 10^5, 0 \le x, y \le 10^8, 0 \le z \le 1000).
Each of the next lines contains two integers a_i and b_i, describing the initial and desired amounts of dirt in flowerbed .
Print the minimum total cost Farmer John needs to spend to complete his landscaping project.
Example 1