Some alternative artists have recently made some ugly graffitis on a long wall of yours. You know the exact location of the graffitis. For instance, if one is at location 2, this means that the second unit of the wall is all painted with a graffiti.

Instead of removing the graffitis, you prefer to just cover them.
A shop sells you *p* panels, each ℓ units long,
for a total price of *p* × ℓ.
You can choose ℓ, but *p* is fixed.
The panels cannot be cut into smaller pieces.
Minimize the cost of covering all the graffitis.

**Input**

Input consists of several cases,
each with the number of graffitis *g*,
followed by *g* different locations (all between 1 and 10^{9}),
followed by *p*.
Assume 2 ≤ *g* ≤ 10^{5} and 1 ≤ *p* ≤ *g*.

**Output**

For every case, print the minimum cost to cover all the graffitis.

Public test cases

**Input**

3 2 9 7 3 3 2 9 7 2 3 2 9 7 1 2 1 1000000000 1

**Output**

3 6 8 1000000000

Information

- Author
- Salvador Roura
- Language
- English
- Official solutions
- C++
- User solutions
- C++
- Event
- Novè Concurs de Programació de la UPC - Final
- Date
- 2011-09-21