CF Round #835 Div.4 F题

#include<bits/stdc++.h>
#define int long long
using namespace std;
int t;
int n,c,d;
int a[200003];
long long s[200003];
bool cmp(int a,int b){
	return a>b;
}
signed main(){
	cin>>t;
	while (t--){
		memset(s,0,sizeof(s));
		long long sum=0;
		cin>>n>>c>>d;
		for (int i=1;i<=n;i++){
			cin>>a[i];
			if (i<=d) sum+=a[i];
		}
		if (sum>c){
			printf("Infinity\n");
			continue;
		}
		sort(a+1,a+1+n,cmp);
		if (1LL*a[1]*d<c){
			printf("Impossible\n");
			continue;
		}
		int k=1;
		s[1]=a[1];
		while (d/k*s[k]+s[d%k]>=c){
			k++;
			s[k]=s[k-1]+a[k];
		}
		k-=2;
		cout<<k<<'\n';
	}
	return 0;
}

TLE了，应该这个地方k可能很大

while (d/k*s[k]+s[d%k]>=c){
	k++;
	s[k]=s[k-1]+a[k];
}

想了一个办法二分，但是这个计算要依靠前缀和，怎样才能写出这里的二分qwq

如果正解不是二分的话各位大佬稍微指点一下