USACO US Open Contest 2016 Platinum- 정원 리모델링 > 문제은행 : 정보올림피아드&알고리즘




3631 : 정원 리모델링

제한시간
2000 ms   
메모리제한
512 MB   
해결횟수
2 회   
시도횟수
3 회   

문제

농부 존은 정원을 리모델링하려고 한다. 

농부 존은 N (1 ≤ N ≤ 100,000) 개의 화단을 갖고 있는데, i번 화단에는 Ai송이의 꽃이 있다. 

리모델링이 끝나면 i번 화단에는 Bi송이의 꽃이 있어야 한다. Ai와 Bi는 0 이상 10 이하의 정수이다.

 

꽃을 옮기는 방법은 여러 방법이 있다. 한 화단에 꽃 하나를 심는 데에는 X원이, 

꽃 하나를 버리는 데에는 Y원이, i번 화단에 있는 꽃 하나를 j번 화단으로 옮기는 데에는 Z×|i-j|원이 든다. 

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

 


입력형식

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

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

 


출력형식

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

 


입력 예

4 100 200 1
1 4
2 3
3 2
4 0

출력 예

210


경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP