#include <stdio.h>#include <iostream>#include <string.h>#include <cmath>#include <vector>#include <set>#include <map>#include <algorithm>#include <queue>#include <string>using namespace std;typedef long long ll;typedef pair<int,int> pii;#define sfll(x) scanf("%lld",&x)#define sfint(x) scanf("%d",&x)#define sfstr(c) scanf("%s",c)#define fr(i,s,n) for(int i=s;i<n;++i)#define cl(a) memset(a,0,sizeof(a))using namespace std;namespace SOL { const int N = 100010; ll cnt[N]; ll sumcnt[N]; ll sum2icnt[N]; ll sumiicnt[N]; int n,k; ll rair; ll m[N]; void cal(ll i,ll p){ ll res=0; while(rair && ( rair - i ) * (rair - i) >p){ rair--; } ll ad = (p - ll(i)*ll(i)) * (sumcnt[i+1] -sumcnt[rair+1]); ad -= sumiicnt[i+1] - sumiicnt[rair+1]; ad += i * (sum2icnt[i+1] - sum2icnt[rair+1] ); ll tmp = m[i] - ad; if(tmp < 0){ cnt[i] = 0; } else{ cnt[i] = (tmp+1) / p; if( (tmp + 1) % p != 0) cnt[i]++; } } bool check(ll p){ rair = n; sumcnt[n+1] = 0; sum2icnt[n+1] = 0; sumiicnt[n+1] = 0; for(int i = n;i;--i){ cal(i,p); sumcnt[i] = sumcnt[i+1] + cnt[i]; if(sumcnt[i] > k) return 0; sum2icnt[i] = sum2icnt[i+1] + 2*((ll)i)*cnt[i]; sumiicnt[i] = sumiicnt[i+1] + (ll(i) * ll(i)) * cnt[i]; } return 1; } void sol() { int t; sfint(t); while(t--){ sfint(n);sfint(k); fr( i , 1 ,n+1){ sfll(m[i]); } ll l = 1,h = 6,mid; h = 1LL<<40; ll ans = 0; while(l <= h){ mid = (l+h)/2; if(check(mid)){ h = mid-1; ans = mid; } else l = mid+1; } printf("%lldn",ans); } }}int main() { SOL::sol(); return 0;}
