Drinking Water

There is an array of $n$ real numbers. The $i$-th number is $h_i$. Initially, all $h_i$ are distinct.

In each operation, you may choose any number of the $h_i$ and set the value of each chosen $h_i$ to the average of the chosen numbers. The chosen numbers do not need to be consecutive. For example, you may choose $h_1$ and $h_3$ without choosing $h_2$. You may apply the operation at most $k$ times.

Find the maximum possible value of $h_1$.

The first line contains three positive integers $n$, $k$, and $p$. They are the length of the array, the maximum number of operations, and the required precision.

The second line contains $n$ positive integers. The $i$-th integer is $h_i$. All $h_i$ are distinct, and $1 \le h_i \le 10^5$.

Print the maximum possible $h_1$ as a real number on one line. The integer part is required. Print the decimal point only if there is a decimal part. You may print at most $2p$ digits after the decimal point, and at least $p$ digits is recommended. The reference answer differs from the true answer by at most $10^{-2p}$.

Your answer is correct if its absolute difference from the reference answer is less than $10^{-p}$. If the difference is at least $10^{-p}$ but less than $10^{-5}$, you receive 40% of the points for that test case.

For all test cases, $3 \le p \le 3000$, $1 \le n \le 8000$, and $1 \le k \le 10^9$.

To guarantee precision, keep more than $p$ digits after the decimal point in arithmetic operations when possible. The reference solution for each subtask keeps the absolute error below $10^{-p}$ when each operation keeps at most $\frac{6}{5}p$ digits after the decimal point.

A high-precision library, library.zip, is provided. Using it is optional.

The Decimal library supports addition, subtraction, multiplication, division, comparison, and conversion to and from double, integers, and strings. For multiplication and division, one operand must be an integer. You cannot multiply or divide two Decimal values.

The library defines the constant $P$, the maximum absolute error of each operation, which is $10^{-P}$. In the C++ version, line 9 of drink_sample.cpp sets it with const int PREC = 2100;. In the C version, line 9 of drink_sample.c sets it with #define PREC 2100. In the Pascal version, lines 8 and 14 of drink_sample.pas both contain 2100. If you change $P$, change every occurrence to the same value. Each operation takes $O(P)$ time. Each Decimal instance takes at most $\frac{4P}{9}+16$ bytes.

When calling Decimal functions, follow these conditions:

• Every intermediate Decimal value has an absolute value of at most $10^{18}$.
• int and longint arguments have absolute values of at most $10^9$.
• long long and int64 arguments have absolute values of at most $10^{18}$.
• A double argument is a valid real number with absolute value at most $10^9$.
• A string argument is a valid real number. A negative number starts with a minus sign, and a non-negative number has no sign. It has an integer part, then a decimal point, then a decimal part. The decimal point and decimal part may both be omitted. Its absolute value is at most $10^9$.
• Do not divide by zero.
• When converting a Decimal to a string, the number of digits after the decimal point must be greater than zero. In C, allocate enough space for the string returned by to_string_d(Decimal, char*, int).

The programs drink_sample.cpp/c/pas contain only the library. You may work on them directly, but you do not have to. The programs decimal_test.cpp/c/pas show how to use the Decimal library and each of its functions.