Graffiti covering P67710


Statement
 

pdf   zip

html

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 109), followed by p. Assume 2 ≤ g ≤ 105 and 1 ≤ pg.

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