케이크

지민이는 케이크 조각 N개를 가지고 있다. 각 조각의 무게는 양수이며, 서로 같을 수도 있고 다를 수도 있다. 지민이는 조각을 최대 M번 자를 수 있다. 한 번 자르면 현재 있는 조각 하나를 골라, 무게의 합이 원래 조각의 무게와 같은 두 개의 양수 무게 조각으로 나눈다.

모든 자르기를 마친 뒤 가장 무거운 조각과 가장 가벼운 조각의 무게 차이를 생각하자. 이 차이가 최소가 되도록 할 때의 값을 출력한다.

첫째 줄에 케이크 조각의 개수 N이 주어진다. N은 50보다 작거나 같다.

둘째 줄에 N개 조각의 무게가 주어진다. 각 무게는 1,000,000,000보다 작거나 같은 자연수이다.

셋째 줄에 자를 수 있는 최대 횟수 M이 주어진다. M은 100,000보다 작거나 같은 자연수이다.

가장 무거운 조각과 가장 가벼운 조각의 무게 차이의 최솟값을 출력한다.

절대 오차 또는 상대 오차가 $10^{-9}$ 이하이면 정답으로 인정된다.