Cake

Jimin has N pieces of cake. Each piece has a positive weight, and different pieces may have the same or different weights. Jimin may make at most M cuts. One cut chooses one current piece and divides it into two positive-weight pieces whose weights sum to the original weight.

After all cuts are finished, consider the difference between the heaviest and lightest remaining pieces. Output the minimum possible value of this difference.

The first line contains the number of cake pieces N, where N is at most 50.

The second line contains the weights of the N pieces. Each weight is a positive integer not greater than 1,000,000,000.

The third line contains M, the maximum number of cuts. M is a positive integer not greater than 100,000.

Print the minimum possible difference between the heaviest and lightest pieces.

An absolute or relative error of at most $10^{-9}$ is accepted.