记录编号	578536	评测结果	AAAAAAAAAAA
题目名称	[USACO23 Feb Silver] Bakery	最终得分	100
用户昵称	ムラサメ	是否通过	通过
代码语言	C++	运行时间	0.004 s
提交时间	2023-03-28 14:26:07	内存使用	1.07 MiB

#include<bits/stdc++.h>
using namespace std;
long long T;
long long n,tc,ttm;
struct Node{
	long long a,b,c;
}w[110];
long long c[110];
bool check(long long x){
	long long Max=0,Min=0x3f3f3f3f;
	for(long long i=1;i<=n;i++){
		long long m=w[i].c-x*w[i].b;
		if(c[i]>0){
			Min=min((m/c[i]),Min);
		}
		else{
			if(c[i]==0){
				if(m<0){
					return false;
				}
			}
			else{
				if(c[i]<0){
					long long q=0;
					if(m%c[i]){
						q=1;
					}
					Max=max(m/c[i]+q,Max);
				}
			}
		}
	}
	if(Max>Min||Max>=x||Max>tc||Min<1||Min<x-ttm){
		return false;
	}
	return true;
}
signed main(){
	freopen("bakery.in","r",stdin);
	freopen("bakery.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>T;
	while(T--){
		cin>>n>>tc>>ttm;
		for(long long i=1;i<=n;i++){
			long long x,y,z;
			cin>>x>>y>>z;
			w[i].a=x;
			w[i].b=y;
			w[i].c=z;
			c[i]=x-y;
		}
		long long l=2,r=ttm+tc;
		while(l<=r){
			long long mid=l+r>>1;
			if(check(mid)){
				l=mid+1;
			}
			else{
				r=mid-1;
			}
		}
        long long ans=ttm+tc-r;
		cout<<ans<<endl;
	}
	return 0;
}