A. Powerbank
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

A group of $$$n$$$ friends went to Troodos mountains for hiking. Each friend has a phone, and the $$$i$$$-th phone initially has a charge of $$$a_i$$$ units. All phones are of the same model, and the maximum battery capacity for each phone is $$$M$$$ units.

They also have a single power bank with a total charge capacity of exactly $$$n \cdot M$$$ units, which is sufficient to fully charge all $$$n$$$ phones to their maximum.

However, the power bank can only be connected to one phone at a time. It can be reconnected to different phones as needed.

Friends are a bit tired, so they can't switch the power bank from one phone to another too often. The maximum number of switches is some given integer $$$S$$$.

For risk management, friends also came up with a rule that at any point in time during the charging process, the difference in charge between any two phones should not exceed $$$D$$$ units.

Your task is to find the minimum possible value of $$$D$$$ such that it is possible to fully charge all phones while satisfying both rules. Note that the answer may be non-integer and also in some cases such $$$D$$$ doesn't exist. See output section for more details.

Input
  • The first line contains three integers: $$$n$$$, $$$M$$$, and $$$S$$$ ($$$2 \leq n \leq 2\cdot 10^5$$$, $$$1 \leq M \leq 10^{18}$$$, $$$0 \leq S \leq 10^{18}$$$).
  • The second line contains $$$n$$$ integers: $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \leq a_i \leq M$$$), where $$$a_i$$$ is the initial charge of the $$$i$$$-th phone.
Output

If it is not possible to meet the above conditions for any value of $$$D$$$, output $$$-1$$$, otherwise output one real number $$$D$$$. Your answer is considered correct if its absolute or relative error does not exceed $$$10^{-6}$$$. Formally, let your answer be $$$a$$$, and the jury's answer be $$$b$$$. Your answer is accepted if and only if $$$\frac{|a-b|}{\max(1, |b|)} \le 10^{-6}$$$

Scoring

This task contains six subtasks. To get the points for the subtask, your solution should pass all the tests in the corresponding subtask.

SubtaskConstraintsPoints
$$$1$$$$$$a_i = 0$$$$$$10$$$
$$$2$$$$$$S \leq 10^6$$$$$$25$$$
$$$3$$$$$$n \leq 2$$$$$$9$$$
$$$4$$$$$$n \leq 3$$$$$$12$$$
$$$5$$$$$$n \geq 10$$$, $$$S = 10^9$$$, $$$M = 10^{18}$$$, $$$a_i$$$ are randomly generated$$$8$$$
$$$6$$$no additional constraints$$$36$$$
Examples
Input
2 7 2
0 0
Output
3.5
Input
4 10 1
7 8 9 10
Output
-1
Input
3 5 5
1 2 3
Output
2
Note

In the first example, we should charge the first phone to $$$3.5$$$ units, then fully charge the second phone, then fully charge the first phone.