Description

In Flea country there are $n$ cities and the great flea king lives in the capital of the flea country, namely city $1$.

The biggest problem in the flea country is drinking water. Because there are too many fleas living in the capital, the flea king compassionately distributes the water allocated to him to the residents of the flea country to drink, which often causes the flea king to go thirsty.

As a result, the Flea nation built a cylindrical water tank in each city. These water tanks are identical and sufficiently high. After a rainy day, the first $i$ cities have collected a height of $h_i$ water. Due to the influence of geography and weather, the height of water collected in any two different cities is different from each other.

The flea king also invited ant craftsmen to help, and built a huge underground connection system. Every time the flea king uses the underground connection system, he can connect the water tanks of as many cities as he wants. After connecting the water tanks of these cities with the underground connection system for a long enough time, the underground connection system can be closed. After this operation, the water in the water tanks in all connected cities will reach the same height, and this height is equal to the average of the heights of the specified water tanks.

Due to the complexity of the underground connection system, the flea king can only use $k$ underground connection system.

Please tell the flea king the highest possible water level in the water tank of city $1$ using atmost $k$ underground connection systems.

Input Format

The first line of input contains three positive integers $n,k,p$, representing the number of cities in the flea country, the maximum number of times the flea king can use the underground connection system, and the accuracy required by the answer you output respectively. The meaning of $p$ will be explained in the output format.

The next line contains $n$ positive integers where each positive integer $h_i$ represents the water level of the $i$-th city's water tank after the rain. It is guaranteed that the level of water for two cities is different and $1 \leq h_i \leq 10^5$.

Output Format

Output only one real number in one line, which is the highest possible level in the water tank of city $1$.

This real number can only contain non-negative integer part, decimal point, and decimal part. The non-negative integer part is a necessary part, and no sign is added. If there is a decimal part, the non-negative integer part and the decimal part are separated by a decimal point. If there is no decimal part, no decimal point is added.

The real number you output cannot have more than $2p$ digits after the decimal point. It is recommended to keep at least $p$ bits. Test data guarantees that the absolute error between the reference answer and the real answer is less than $10^{-2p}$.

Your output is judged to be correct if and only if the absolute error between your output and the reference answer is less than $10^{-p}$.

If the absolute error between your output and the reference answer is not less than $10^{-p}$ but less than $10^{-5}$, you will get $40\%$ score.

3 1 3
1 4 3

2.666667

Since the underground connection system is used at most once, there are five options:

1. To not use underground connection system: In this case the water tank level of the city $1$ is $1$.
2. Use the one-time connection systemt to connect cities $1$,$2$: In this case the water tank level of the city $1$ is $5/2$.
3. Use the one-time connection system to connect cities $1$,$3$: In this case the water tank level of the city $1$ is $4/2$.
4. Use the one-time connection system, connect cities $2$,$3$: In this case the water tank level of the city $1$ is $1$.
5. Use the one-time connection system, connect cities $1$,$2$,$3$: In this case the water tank level of the city $1$ is $8/3$.

3 2 3
1 4 3

3.000000

In this case, the optimal solution is to use two connected systems, the first connection between cities $1,3$, and the second connection between cities $1,2$.

Sample 3

See attached files 3.in and 3.out

Constraints

In order to ensure the accuracy of the answer, we generally need to keep more than $p$ decimal places. It can be proved that if it is guaranteed that in the reference algorithm, at any time the answer is retained with $\frac{6}{5}p$ decimal places, the absolute error between the output obtained for any input and the reference answer is less than $10^{-p}$.

In order to facilitate the participants to handle high-precision decimals, we provide fixed-point high-precision decimals. Participants can refer to and use this category according to their own needs, or not use this category at all. For specific usage, please refer to the issued document decimal.pdf.

All test data, satisfies $1 \le n \le 8000,1 \le k \le {10} ^ 9, 3 \le p \le 3000$.