ページが読み込まれませんか？ こちらをクリックすると直るかもしれません。
Placeholder

#3631

정원 리모델링 (Hard) 2s 512MB

問題

농부 존은 정원을 리모델링하려고 한다. 농부 존은 N (1 ≤ N ≤ 100\,000) 개의 화단을 갖고 있는데, i번 화단에는 A_i송이의 꽃이 있다. 리모델링이 끝나면 i번 화단에는 B_i송이의 꽃이 있어야 한다. A_i와 B_i는 0 이상 10 이하의 정수이다.

꽃을 옮기는 방법은 여러 방법이 있다. 한 화단에 꽃 하나를 심는 데에는 X원이, 꽃 하나를 버리는 데에는 Y원이, i번 화단에 있는 꽃 하나를 j번 화단으로 옮기는 데에는 Z×|i-j|원이 든다. 

농부 존을 도와 정원을 리모델링하는 최소 비용을 구하는 프로그램을 작성하여라.


入力

첫 번째 줄에는 N, X, Y, Z가 주어진다. (0 ≤ X, Y ≤ 10^8; 0 ≤ Z ≤ 1\,000).

두 번째 줄부터 N개의 줄에는 A_i, B_i가 주어진다.


出力

첫 번째 줄에 정원을 리모델링하는 최소 비용을 출력한다.


例題 

4 100 200 1

1 4

2 3

3 2

4 0
210

出典

USACO 2016 US Open Platinum

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