B. Average Superhero Gang Power

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 nn superheroes in avengers team having powers a1,a2,…,ana1,a2,…,an, 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 11. They can do at most mm operations. Also, on a particular superhero at most kk operations can be done.

Can you help the avengers team to maximize the average power of their crew?

Input

The first line contains three integers nn, kk and mm (1≤n≤1051≤n≤105, 1≤k≤1051≤k≤105, 1≤m≤1071≤m≤107) — 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 nn integers a1,a2,…,ana1,a2,…,an (1≤ai≤1061≤ai≤106) — the initial powers of the superheroes in the cast of avengers.

Output

Output a single number — the maximum final average power.

Your answer is considered correct if its absolute or relative error does not exceed 10−610−6.

Formally, let your answer be aa, and the jury's answer be bb. Your answer is accepted if and only if |a−b|max(1,|b|)≤10−6|a−b|max(1,|b|)≤10−6.

Examples

input

2 4 6
4 7

output

11.00000000000000000000

input

4 2 6
1 3 2 3

output

5.00000000000000000000

题意：有n个超级英雄，每个英雄的力量可以提高最多k次，所有英雄力量的提高和删除的次数不大于m次。求超级英雄的平均最大力量是多少。

思路：对力量进行排序，依次删除最小的值，求得当前平均力量，取最大值。

注意点：删除也占用操作次数，n与k相乘时需开long long

代码：

#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<cstdio>
#include<cmath>
#include<set>
#include<map>
using namespace std;
#define ll long long
#define inf 0x3f3f3f3f
#define mem(a,b) memset(a,b,sizeof(a))
#define closeio std::ios::sync_with_stdio(false)
 
int a[100005],n,k,m;
double s;


double power(int i)
{
	if((ll)(n-i)*k<=m)
		return (s+(ll)(n-i)*k)/(n-i);
	else
		return (s+m)/(n-i);
}

int main()
{
	int i;
	s=0;
	cin>>n>>k>>m;
	for(i=1;i<=n;i++)
	{
		cin>>a[i];
		s+=a[i];
	}
	double Max=(s+min((ll)n*k,(ll)m))/n;
	sort(a+1,a+n+1);
	for(i=1;i<=n-1;i++)
	{
		s-=a[i];
		m--;
		Max=max(Max,power(i));
		if(m<=0)
			break;
	}
	printf("%.12lf\n",Max);
	return 0;
}

【CF 1111B】Average Superhero Gang Power

B. Average Superhero Gang Power