ページが読み込まれませんか？ こちらをクリックすると直るかもしれません。
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

ログインしないとコードを書けません。