Average Superhero Gang Power

题意翻译

给出n,k,m和n个数,表示每个人的能力值。进行m次操作,每次操作可以删掉一个人(至少有两个人)或者给一个人的能力值+1,且每个人能力值加的次数不能超过k。问最后所有剩下的人的能力值的平均的最大值。

题目描述

Every superhero has been given a power value by the Felicity Committee. The avengers crew wants to maximize the average power of the superheroes in their team by performing certain operations. Initially, there are $ n $ superheroes in avengers team having powers $ a_1, a_2, \ldots, a_n $ , respectively. In one operation, they can remove one superhero from their team (if there are at least two) or they can increase the power of a superhero by $ 1 $ . They can do at most $ m $ operations. Also, on a particular superhero at most $ k $ operations can be done. Can you help the avengers team to maximize the average power of their crew?

输入输出格式

输入格式


The first line contains three integers $ n $ , $ k $ and $ m $ ( $ 1 \le n \le 10^{5} $ , $ 1 \le k \le 10^{5} $ , $ 1 \le m \le 10^{7} $ ) — the number of superheroes, the maximum number of times you can increase power of a particular superhero, and the total maximum number of operations. The second line contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 1 \le a_i \le 10^{6} $ ) — the initial powers of the superheroes in the cast of avengers.

输出格式


Output a single number — the maximum final average power. 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} $ .

输入输出样例

输入样例 #1

2 4 6
4 7

输出样例 #1

11.00000000000000000000

输入样例 #2

4 2 6
1 3 2 3

输出样例 #2

5.00000000000000000000

说明

In the first example, the maximum average is obtained by deleting the first element and increasing the second element four times. In the second sample, one of the ways to achieve maximum average is to delete the first and the third element and increase the second and the fourth elements by $ 2 $ each.