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

#3776

정원 리모델링 1s 128MB

문제

농부 존은 정원을 리모델링하려고 한다. 농부 존은 N (1 ≤ N ≤ 100) 개의 화단을 갖고 있는데, 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, Z ≤ 1000).

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


출력

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


예제 

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

입력 세부 정보

일렬로 놓인 4개의 화단에는 처음에는 꽃이 각각 1, 2, 3, 4송이 있다. 농부 존은 이 화단의 꽃을 각각 4, 3, 2, 0송이로 바꾸려고 한다. 꽃을 심고, 버리고, 옮기는 비용은 각각 100, 200, 1이다.

출력 세부 정보

화단 4에서 꽃 1송이를 버려야 하며, 200의 비용이 든다. 나머지 꽃은 10의 비용으로 옮길 수 있다 (화단 4에서 화단 1로 3송이, 화단 3에서 화단 2로 1송이).


출처

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