#include "ricehub.h"
#include "bits/stdc++.h"
using namespace std;
const int maxn = 100005;
using ll = long long;
int a[maxn];
ll lim;
vector<ll> p;
int n;
bool can(int x){
ll tot = LLONG_MAX;
for(int i = x - 1; i < n; ++i){
int l = i - x + 1;
ll val;
if(l != 0){
val = p[i] - p[l - 1];
}else {
val = p[i];
}
val /= x;
ll need = 0;
for(int j = l; j <= i; ++j){
need += llabs(a[j] - val);
}
tot = min(tot, need);
need = 0;
for(int j = l; j <= i; ++j){
need += llabs(a[j] - (val + 1));
}
tot = min(tot, need);
}
if(tot <= lim)return 1;
else return 0;
}
int besthub(int R, int L, int X[], long long B)
{
n = R;
lim = B;
p.resize(R);
for(int i = 0; i < R; ++i){
a[i] = X[i];
}
sort(a, a + R);
for(int i = 0; i < R; ++i){
if(i == 0){
p[i] = a[i];
}else {
p[i] = p[i - 1] + a[i];
}
}
int ans = 0;
int lo = 1, hi = R;
while(lo <= hi){
int mid = (lo + hi) >> 1;
if(can(mid)){
ans = mid;
lo = mid + 1;
}else {
hi = mid - 1;
}
}
return ans;
}
