Graffiti covering P67710

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⁹), followed by p. Assume 2 ≤ g ≤ 10⁵ and 1 ≤ p ≤ g.

Output

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