Minimum Moving Cost

Mr.sb runs a moving company and has N items with moving costs a₁, a₂, ..., a_N. He devised a special pricing scheme: in each operation you may pick any 2 items and combine them. The cost to move the combined item is computed as

$$ \text{merge}(x,y)=\frac{x+y}{k}, $$

where x and y are the costs of the two items chosen and k is a given positive constant. The merged item then replaces the two items. You continue performing such merge operations until only one item remains; the final cost of that item is the price to be paid.

The twist is that the order in which you combine items is under your control. Since Mr.sb wishes to minimize the cost (so that more money can be donated to charity), you are asked to compute the minimum cost achievable by an optimal merge order.

Hint: Because the merge operation is linear, the final cost can be written as a weighted sum of the original costs where each merge operation introduces a division by k. To minimize the final cost when k > 1, it is best to merge the more expensive items as early as possible so that they are divided more times. An optimal strategy is to first sort the items in descending order and then merge them sequentially from largest to smallest, i.e. let

$$ \text{ans} = \frac{\cdots\Bigl(\frac{\frac{(d_1+d_2)}{k}+d_3}{k}+d_4\Bigr)}{k}\, , $$

where d₁ ≥ d₂ ≥ d₃ ≥ ... ≥ d_N is the sorted order of costs.

inputFormat

The first line contains two integers N and k (1 ≤ N ≤ 10⁵, 1 ≤ k ≤ 10⁹), where N is the number of items and k is the divisor in the merge operation.

The second line contains N space‐separated positive integers a₁, a₂, ..., a_N representing the moving cost for each item.

outputFormat

Output a single floating point number denoting the minimum cost achievable after performing N-1 merge operations optimally. The answer should be accurate up to 6 decimal places.

sample

3 2
3 2 1

1.750000