### Problem Statement

You have been assigned to deliver a number of packages from a warehouse to various destinations along a straight line. At the beginning, all the packages are at the warehouse, which is at the left end of the line. You and your truck are also at the warehouse.

Your truck has room for truckCapacity packages. Driving the truck costs fuelCost dollars per mile, regardless of the number of packages on the truck. You may park the truck anywhere you'd like, but each time you park somewhere other than at the warehouse, it costs parkingCost dollars. The truck must always be parked while you deliver a package to its destination. In other words, you cannot drop packages from a moving truck. You may never leave packages anywhere other than at their destinations, at the warehouse, or in the truck.

You can also carry packages on foot, but you can only carry one package at a time. It costs walkCost dollars per mile to walk while carrying a package. Walking without carrying anything costs nothing.

You are given a int[] packages, each element of which is the distance (in miles) of a package's destination from the warehouse. You must deliver all the packages, but you do not have to return the truck to the warehouse. Return the minimal cost required to do this.

### Definition

 Class: PackageDelivery Method: minimalCost Parameters: int[], int, int, int, int Returns: long Method signature: long minimalCost(int[] packages, int walkCost, int fuelCost, int parkingCost, int truckCapacity) (be sure your method is public)

### Constraints

-packages will contain between 1 and 50 elements, inclusive.
-Each element of packages will be between 1 and 1000000, inclusive.
-walkCost, fuelCost and parkingCost will each be between 0 and 1000000, inclusive.
-truckCapacity will be between 1 and 50, inclusive.

### Examples

0)

 `{ 1, 2, 3 }` `3` `2` `3` `3`
`Returns: 13`
 One of the best possible ways is to load all packages onto the truck, then park it at point 2 and walk from there.
1)

 `{ 1, 2, 3, 4, 5 }` `3` `2` `3` `5`
`Returns: 23`
 Here, one of the best ways is to load all the packages onto the truck and then park it two times - first, at point 2, then, point 4.
2)

 `{ 1, 2, 3, 4, 5 }` `11` `5` `9` `2`
`Returns: 91`
3)

 `{ 5, 5, 5 }` `1` `1` `1` `3`
`Returns: 6`
 Note that elements of packages don't have to be distinct.
4)

 `{ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }` `1` `3` `10` `5`
`Returns: 53`

#### Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=7927

#### Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10777&pm=7927

mateuszek

#### Testers:

PabloGilberto , Olexiy , lovro , ivan_metelsky

#### Problem categories:

Dynamic Programming