Long Jump Training

During a sports meet, Xiao Ming performs a standing long jump on a number line starting at the origin. There are n required checkpoints \(a_1, a_2, \cdots, a_n\) with \(a_i \ge a_{i-1} > 0\). He must jump to each checkpoint in order and is only allowed to land exactly on a checkpoint. In addition, he may add up to m extra checkpoints of his choice to make his jumps easier.

Before the meet, Xiao Ming plans his training so that his maximum jump in a single attempt reaches a distance \(L\). He has also learned an explosive technique which can be used exactly once during the competition; when used, his maximum jump distance for that particular jump becomes \(2L\). He wonders: what is the minimum value of \(L\) such that, by optimally inserting at most m extra checkpoints and using the explosive move once, he can complete the course?

Note on the mechanics:

• The course consists of the starting position \(0\), the n required checkpoints, and any extra checkpoints you choose to add.
• For any jump with a distance \(d\), if Xiao Ming does not use the explosive move then he must have \(d \le L\). If he chooses to use his explosive move for that jump, then the jump can be as long as \(2L\).
• You are allowed to place extra checkpoints arbitrarily between the given ones. When planning the jumps between two consecutive checkpoints in your chosen sequence, you may add as many intermediate extra checkpoints as needed. The number of extra checkpoints used (over all gaps) must not exceed \(m\).

Mathematically, consider the gaps between consecutive points in the sequence (including the gap from \(0\) to \(a_1\)). Without the explosive move, for a gap of length \(d\) the minimum number of extra checkpoints required is
\(c_{normal}(d) = \lceil \frac{d}{L} \rceil - 1\).
If the explosive move is used on that gap, then if \(d \le 2L\) no extra checkpoint is needed; otherwise the extra checkpoints required become
\(c_{explosive}(d) = \lceil \frac{d-2L}{L} \rceil\).
Since the explosive move can be applied to at most one gap, the overall extra checkpoints needed is
\(\sum_{i} c_{normal}(d_i) - \max_{i}(c_{normal}(d_i) - c_{explosive}(d_i))\),
and this must not exceed \(m\).

inputFormat

The first line contains two integers: n and m (\(1 \le n \le 10^5\), \(0 \le m \le 10^9\)).

The second line contains \(n\) integers \(a_1, a_2, \cdots, a_n\) (\(1 \le a_i \le 10^9\)) in non-decreasing order.

outputFormat

Output the minimum value of \(L\) required, printed with 6 decimal places.

sample

3 0
2 6 10

4.000000