16403번 - 놀이동산

준용이는 ㅇㅇ신도시에 새로 오픈할 놀이동산인 Seungbum Amusement Park, 줄여서 SAP의 홍보팀 브레인이다. 준용이는 미리 입장권을 예약한 ㅇㅇ시 시민들에게 교통비를 제공하는 이벤트를 준비중이다. 하지만 깐깐한 SAP의 재무팀은 경비를 최소로 하지 않으면 이벤트를 진행할 수 없다는 입장이다. 이정도 계산은 준용이에게 너무 쉬운 문제지만 계산을 어려워하는 팀원을 위해 프로그램으로 만들려고 한다.

ㅇㅇ시는 0번부터 10,000번까지 순서대로 도로를 따라 있는 블록으로 이루어져 있고, 놀이동산은 0번 블록에 있다.

ㅇㅇ시의 교통수단은 택시와 셔틀버스 두 가지밖에 없다.

택시는 기본 요금 없이 한 블록을 이동할 때 마다 비용이 추가되는 완벽한 거리비례 요금제로서, 한 블록을 이동하는데 A원을 낸다. 하지만 이런 합리적인 요금제를 위해 비용을 절감한 결과 ㅇㅇ시의 택시는 손님이 한 명 밖에 탈 수 없는 크기가 되어버렸다.

셔틀버스는 거리에 상관 없이 B원을 내면 40명까지 사용 가능하다. 하지만 중간에 정차하지 않고 특정 블록에서 바로 놀이동산으로 이동한다.

예를 들어, 블록당 택시요금 A=1원, 버스요금 B=20원이고, 입장권을 예약한 7명의 사람이 각각 10번, 30번, 20번, 10번, 90번, 100번, 110번 블록에 산다고 하자. 7명의 사람이 모두 택시를 타고 이동하면 370원의 비용이 든다. 하지만 적절한 위치에 버스를 부르면 다음과 같이 비용을 줄일 수 있다.

1. 20번 블록에 사는 사람이 30번 블록으로 택시를 타고 간 후, 30번 블록에서 두 사람이 버스를 타고 놀이공원으로 이동한다. 그 비용은 총 30원이다.
2. 90번과 110번 블록에 사는 사람이 100번 블록으로 택시를 타고 간 후, 100번 블록에서 세 사람이 버스를 타고 놀이공원으로 이동한다. 그 비용은 총 40원이다.
3. 10번 블록에 사는 두 사람이 버스를 타고 이동한다. 그 비용은 총 20원이다. 두 명이 따로 택시를 타고 가도 20원으로 결과는 같다.

위의 경우 총 90원의 비용으로 모두 놀이동산에 도착할 수 있다.

놀이동산을 예약한 시민의 수 N, 각 시민이 살고 있는 블록, 한 블록당 추가되는 택시비용 A, 버스 비용 B가 주어졌을 때 드는 경비의 최솟값을 구하는 프로그램을 작성하시오.

첫째 줄에 놀이동산을 예약한 시민의 수 N(1 ≤ N ≤ 10000)이 주어진다.

둘째 줄에는 한 블록당 추가되는 택시 비용 A와 버스를 예약할 때 드는 비용 B가 빈칸을 사이에 두고 차례로 주어진다. (0 ≤ A ≤ 1,000, 0 ≤ B ≤ 100,000)

셋째 줄에 각 시민이 사는 블록의 번호가 주어진다.

첫째 줄에 모든 인원이 놀이동산으로 이동하는데 드는 총 경비의 최솟값을 출력한다.