택배

진영 택배 회사는 물품을 빠르고 정확하게 배송하기로 유명하다. 본점에 모인 물품은 각각 지정된 지점으로 배송되어야 한다. 본점은 고속도로가 시작되는 곳에 있고, 지점들은 1번부터 10,000번까지 번호 순서대로 고속도로를 따라 일정한 간격으로 놓여 있다.

물품을 옮기는 방법은 트럭과 헬리콥터 두 가지이다. 트럭은 본점에서 지점으로, 또는 한 지점에서 다른 지점으로 물품을 옮길 수 있다. 트럭으로 물품 하나를 운반하는 비용은 운송 거리에 비례한다. 헬리콥터는 본점에서 지점으로만 물품을 옮길 수 있고, 한 번 이용하는 비용은 물품의 개수와 운송 거리에 관계없이 일정하다. 트럭은 한 번에 물품 하나만 운반할 수 있지만, 헬리콥터가 한 번에 운반할 수 있는 물품 수에는 제한이 없다. 회사에는 항상 충분한 수의 트럭과 헬리콥터가 있다고 가정한다.

예를 들어, 본점에 10번, 40번, 30번, 50번, 10번 지점으로 보내야 하는 물품 5개가 접수되었다고 하자. 물품 하나를 트럭으로 한 지점 간격 옮기는 비용이 10이고, 헬리콥터를 한 번 이용하는 비용이 200이면, 모든 물품을 트럭으로만 옮기는 비용은 1400이다. 하지만 10번 지점으로 갈 두 물품은 트럭으로 옮기고, 나머지 세 물품은 헬리콥터로 함께 40번 지점까지 옮길 수 있다. 그러면 40번 지점으로 갈 물품은 도착한 상태이고, 30번과 50번 지점으로 갈 물품만 40번 지점에서 각각 트럭으로 옮기면 되어 총 비용은 600이 된다.

배송할 물품의 총개수, 각 물품의 목적 지점, 트럭과 헬리콥터의 비용이 주어질 때, 모든 물품을 목적 지점으로 옮기는 데 드는 총 비용의 최솟값을 구하는 프로그램을 작성하시오.

첫째 줄에 배송해야 할 물품의 개수 N이 주어진다. (1 <= N <= 3000)

둘째 줄에는 각 물품의 목적 지점 번호가 빈칸을 사이에 두고 주어진다. 지점 번호는 10,000 이하의 자연수이다.

셋째 줄에는 물품 하나를 트럭으로 한 지점 간격 옮기는 데 드는 비용과, 헬리콥터를 한 번 이용하는 데 드는 비용이 차례로 주어진다. 두 비용은 각각 1,000 이하의 자연수이다.

첫째 줄에 모든 물품을 목적 지점으로 옮기는 데 드는 총 비용의 최솟값을 출력한다. 모든 입력에 대해 가능한 배송 방법의 총 비용은 1,000,000,000 이하의 자연수라고 가정해도 좋다.