(*ocaml*) 
(* 
 
Here's how we structure the solution.  First, the 
packages are sorted from left to right, and numbered 
0, ..., n-1. 
 
cost i =  
 
  The minimum cost of starting at 0, delivering packages 0...i and 
  returning the truck to 0.  (Unless i=n-1 then we don't return to 0.) 
 
mult_park_return i j =  
 
  the minimum cost of starting at 0, driving to some point, parking, 
  delivering some packages, moving to the right, delivering more 
  packages, etc, until packages i,i+1...j have been delieverd.  Then 
  return to 0. (Oh, and one of the options considered is parking at 0 
  and doing it all by walking.) 
 
  To compute this we keep an array mp_cost.(k) which is the cost of 
  starting at 0, loading the truck with packages i...j, and delivering 
  the packages up to k, with k being the last parking spot.  If we've 
  computed this for k'<k the way we compute it for k is to consider 
  all k'<k and where k' is the parking spot used before k.  Then add 
  the parking cost, plus the delivery cost for packages between k' and 
  k (using the closest of the two) and adding the round trip travel 
  cost from k' to k.  (Actually we don't need to count the travel 
  cost.  That can be taken into account at the end.) 
 
multi_park_terminal i n-1 
 
  This is exactly the same as multi_park_return, except that we don't 
  return to the start at the end.  We don't pay return driving cost. 
  Actually, the two are folded together in the code, because it does 
  the first if j < n-1 and the 2nd if j=n-1. 
*) 
 
let inf = (max_int/2) 
 
let minf i j f =  
  let rec loop i m = if i>j then m else loop (i+1) (min (f i) m) in 
    loop i inf 
 
let sum i j f =  
  let rec loop i m = if i>j then m else loop (i+1) ((f i) + m) in 
    loop i 0 
 
let solve n p walkCost fuelCost parkCost truckCap =  
  Array.sort compare p; 
  let mp_cost = Array.make n 0 in 
 
  let multi_park i j =  
    for k=i to j do 
      (* k = the last parking spot *) 
      (* we consider two options (1) this is the first parking spot used. 
         (2) we may use another one before me.  Take the minimum of all these options *) 
      let option1 = 
        parkCost 
        + walkCost * (sum i k (fun l -> p.(k) - p.(l))) 
      in 
      let option2 = 
        parkCost 
        + (minf i (k-1)  
             (fun l -> mp_cost.(l) + 
                walkCost * (sum l k (fun m -> min (p.(m)-p.(l)) (p.(k) - p.(m)))))) 
      in 
        mp_cost.(k) <- min option1 option2; 
    done; 
    (* now there are still two options.  (1) Use the above algorithm that parks at least once. 
       (2) walk everything from the start.  We take the best of these two. *) 
    let fcoeff = if j=n-1 then 1 else 2 in 
    let opt1 = minf i j (fun k -> mp_cost.(k) + fcoeff * p.(k) * fuelCost + walkCost * (sum k j (fun m -> p.(m)-p.(k)))) in 
    let opt2 = walkCost * (sum i j (fun k -> p.(k))) in 
      min opt1 opt2 
  in 
   
  let costa = Array.make n (-1) in 
  let rec cost i =  
    if i<0 then 0 else if costa.(i) >= 0 then costa.(i) else 
      let c = minf (max 0 (i-truckCap+1)) i  
        (fun k -> (cost (k-1)) + (multi_park k i)) 
        (* the last delivery uses packages k...i *) 
      in 
        costa.(i) <- c; 
        c 
  in 
    cost (n-1) 
     
let rec main () = 
  let read_int () = Scanf.bscanf Scanf.Scanning.stdib " %d " (fun x -> x) in 
  let n = read_int() in   
    if n=0 then () else 
      let p = Array.make n 0 in 
        for i=0 to n-1 do 
          p.(i) <- read_int () 
        done; 
        let walkCost = read_int() in 
        let fuelCost = read_int() in 
        let parkCost = read_int() in 
        let truckCap = read_int() in 
          Printf.printf "%d\n" (solve n p walkCost fuelCost parkCost truckCap); 
          Printf.printf "%!"; 
          main() 
;; 
 
main ()