//monster #include<bits/stdc++.h> using namespace std; const int N = 5010; int n,m; double a[N],b[N],dp[2][N][N],ans=1e9,w[N]; //dpi,j,k表示第i个数目前总共选了j个，目前总共消耗了k点伤害,第一位可以用滚动数组滚掉 signed main(){ cin>>n>>m; for(int i=1;i<=n;i++){ cin>>a[i]; w[(long long)a[i]]++;//w[x]算出大于等于x的数的个数，用于后面计算贡献 } for(int i=N-9;i>=0;i--){ w[i]+=w[i+1]; } sort(a+1,a+n+1);//将a数组进行排序，因为后面用的剪枝依赖于选择数时的单调性 int len=0; a[0]=-1; for(int i=1;i<=n;i++){ if(a[i]!=a[i-1]){ b[++len]=a[i]; } }//将a数组去重，这样可以降低时间复杂度，避免重复计算一个数的贡献 for(int i=0;i<=n;i++){ for(int j=1;j<=m;j++){ dp[0][i][j]=1e9; } dp[0][i][0]=i*n; }//dp数组预处理，先算出选0的贡献，其余状态设为极大值 for(int i=1;i<=len;i++){ int z=0; if(i>1&&b[i]!=0){ if((n-m/b[i])>0){ z=n-m/b[i]; }//剪枝，当全选这个数才刚好能凑够m点伤害时， //选一些比这个数小的数肯定凑成m所需的个数更多， //所以全选这个数凑成m的个数以下的状态都肯定不会对答案产生贡献 } for(int j=z;j<=n;j++){ for(int k=0;k<=m;k++){ dp[i%2][j][k]=dp[(i-1)%2][j][k]; } }//要先继承讨论到前一个数时的答案 for(int j=z;j<n;j++){ for(int k=0;k<=m-b[i];k++){ dp[i%2][j+1][k+(long long)b[i]]=min(dp[i%2][j+1][k+(long long)b[i]],dp[i%2][j][k]+w[(long long)b[i]+1]); } }//完全背包转移 } for(int i=0;i<=m;i++) ans=min(ans,dp[len%2][n][i]);//计算答案 ans=ans/n; cout<<fixed<<setprecision(9); cout<<ans<<endl; return 0; }