Parcel Delivery

Jinyoung Delivery is known for delivering parcels quickly and accurately. Parcels collected at the headquarters must be delivered to their assigned branches. The headquarters is at the start of a highway, and branches numbered from 1 to 10,000 are placed along the highway at equal intervals.

There are two ways to move parcels: trucks and helicopters. A truck can move one parcel from the headquarters to a branch, or from one branch to another branch. The cost of moving a parcel by truck is proportional to the distance moved. A helicopter can move parcels only from the headquarters to a branch, and the cost of one helicopter trip is fixed regardless of distance or the number of parcels loaded. A truck can carry only one parcel at a time, while a helicopter can carry any number of parcels. Assume the company always has enough trucks and helicopters.

For instance, suppose five parcels must go to branches 10, 40, 30, 50, and 10. Moving one parcel by truck across one branch interval costs 10, and one helicopter trip costs 200. Sending all five parcels only by truck costs 1400. A cheaper plan is to send the two parcels for branch 10 by truck, move the other three parcels together by helicopter to branch 40, and then move the parcels for branches 30 and 50 by truck from branch 40. The total cost is 600.

Given the number of parcels, their destination branches, the truck cost per branch interval, and the fixed cost of one helicopter trip, compute the minimum total cost needed to deliver every parcel to its destination.

The first line contains the number of parcels N (1 <= N <= 3000).

The second line contains N natural numbers separated by spaces, where each number is the destination branch of one parcel. Every branch number is at most 10,000.

The third line contains two natural numbers separated by a space: the cost of moving one parcel by truck across one branch interval, and the cost of using one helicopter trip. Each cost is at most 1,000.

Print the minimum total cost required to deliver all parcels to their destinations. You may assume that for every input, the total cost of any feasible delivery plan is a positive integer not exceeding 1,000,000,000.