#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int MAX_R = 1000005;
long long P[MAX_R];
bool can(int k, int n, const vector<int>& X, long long bgt) {
if (k == 0) return true;
if (k > n) return false;
for (int i = 0; i <= n - k; ++i) {
int lidx = i;
int ridx = i + k - 1;
int midx = lidx + k / 2;
long long cost = 0;
long long nleft = midx - lidx;
long long sleft = P[midx] - P[lidx];
cost += nleft * X[midx] - sleft;
long long nright = ridx - midx;
long long sright = P[ridx + 1] - P[midx + 1];
cost += sright - nright * X[midx];
if (cost <= bgt) {
return true;
}
}
return false;
}
int besthub(int n, int min_k, int x_coords[], long long bgt) {
vector<int> X(x_coords, x_coords + n);
sort(X.begin(), X.end());
P[0] = 0;
for (int i = 0; i < n; ++i) {
P[i+1] = P[i] + X[i];
}
int lo = min_k;
int hi = n;
int res = 0;
while (lo <= hi) {
int md = lo + (hi - lo) / 2;
if (can(md, n, X, bgt)) {
res = md;
lo = md + 1;
} else {
hi = md - 1;
}
}
return res;
}
