페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#3976
채점 보류

Landscaping 2s 512MB

문제

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


입력

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.


출력

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


예제 

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.


출처

USACO 2016 US Open Platinum

로그인해야 코드를 작성할 수 있어요.