/** author: shobonvip created: 2025.03.07 22:05:11 **/ #include<bits/stdc++.h> using namespace std; //* ATCODER #include<atcoder/all> using namespace atcoder; typedef modint998244353 mint; //*/ /* BOOST MULTIPRECISION #include<boost/multiprecision/cpp_int.hpp> using namespace boost::multiprecision; //*/ typedef long long ll; #define rep(i, s, n) for (int i = (int)(s); i < (int)(n); i++) #define rrep(i, s, n) for (int i = (int)(n)-1; i >= (int)(s); i--) #define all(v) v.begin(), v.end() template <typename T> bool chmin(T &a, const T &b) { if (a <= b) return false; a = b; return true; } template <typename T> bool chmax(T &a, const T &b) { if (a >= b) return false; a = b; return true; } template <typename T> T max(vector<T> &a){ assert(!a.empty()); T ret = a[0]; for (int i=0; i<(int)a.size(); i++) chmax(ret, a[i]); return ret; } template <typename T> T min(vector<T> &a){ assert(!a.empty()); T ret = a[0]; for (int i=0; i<(int)a.size(); i++) chmin(ret, a[i]); return ret; } template <typename T> T sum(vector<T> &a){ T ret = 0; for (int i=0; i<(int)a.size(); i++) ret += a[i]; return ret; } ll op(ll a,ll b) { return a + b; } ll e(){ return 0; } void solve() { ll k, n; cin >> n >> k; vector<ll> a(n); vector<ll> b(n); vector<ll> c(n); ll s = 0; rep(i,0,n) { cin >> a[i]; b[i] = a[i] - a[i] / k * k; c[i] = a[i] / k; s += b[i]; } vector<ll> d = c; sort(all(d)); if (s % k != 0) { cout << -1 << '\n'; return; } if (s == 0) { cout << 0 << '\n'; return; } auto check = [&](ll i) { ll p = i + s/k; ll freedom = 0; ll cost = 0; vector<ll> amari(k); rep(i,0,n) { if (b[i] > p) { cost += p; }else { freedom += min(c[i], (p - b[i]) / k); if (a[i] > p) { amari[(p - b[i]) % k] += 1; } cost += b[i]; } } ll left = i; { ll targ = min(freedom, left); freedom -= targ; left -= targ; cost += targ * k; } rrep(i,0,k) { ll targ = min(amari[i], left); left -= targ; amari[i] -= targ; cost += targ * i; } if (p*k<=cost) return true; return false; }; for(ll i=0;i<=min(sum(c),k);i++) { if (check(i)) { cout << i + s/k << '\n'; return; } } ll bsum = sum(b); vector<segtree<ll,op,e>> seg1(k, segtree<ll,op,e>(k+1)); vector<segtree<ll,op,e>> seg2(k, segtree<ll,op,e>(k+1)); vector<bool> seen(k); ll tmp; auto f = [&](ll x) -> bool { return x <= tmp; }; vector ri(k, vector<pair<ll,ll>>(n)); vector<ll> piv(k); for (ll i=k; i<=min(sum(c),n*k+10); i++) { ll p = i+s/k; int var=p%k; if (!seen[var]){ rep(x,0,n){ ri[var][x] = pair(c[x]-(p-b[x])/k, (p-b[x])%k); seg1[var].set(k, seg1[var].get(k) + min(c[x],(p-b[x])/k)); seg2[var].set(k, seg2[var].get(k) + min(c[x],(p-b[x])/k) * k); // not c[x] <= (p-b[x])/k // <=> c[x] - (p-b[x])/k > 0 if (c[x]*k+b[x] > p) { ll am = (p-b[x])%k; seg1[var].set(am, seg1[var].get(am) + 1); seg2[var].set(am, seg2[var].get(am) + am); } } sort(all(ri[var])); while(piv[var]<n && ri[var][piv[var]].first <= i/k-1) piv[var]++; seen[var] = 1; }else{ seg1[var].set(k, seg1[var].get(k) + (n - piv[var])); seg2[var].set(k, seg2[var].get(k) + (n - piv[var]) * k); // now ... c[i] - (p-b[i])/k >= 0 while(piv[var]<n && ri[var][piv[var]].first <= i/k-1) { ll am = ri[var][piv[var]].second; seg1[var].set(am, seg1[var].get(am) - 1); seg2[var].set(am, seg2[var].get(am) - am); piv[var]++; } // now ... c[i] - (p-b[i])/k >= 1 } tmp = i; ll cost = bsum; ll v = seg1[var].min_left(k+1, f); tmp -= seg1[var].prod(v, k+1); cost += seg2[var].prod(v, k+1); assert(tmp >= 0); if (v-1 >= 0){ cost += (v-1) * tmp; } if (p*k<=cost) { cout << p << '\n'; return; } } cout << -1 << '\n'; return; } int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); int t; cin >> t; while(t--) solve(); }