题目链接

#include<bits/stdc++.h>
using namespace std;
struct node{
	int c,d,p;
	long long dp;
}a[1000005];
int cmp(node x,node y){
	return x.dp<y.dp;
}
int f[2][1000005];//滚动数组，循环利用不浪费 
int main(){
	int n;
	long long s;
	scanf("%d%lld",&n,&s);
	for(int i=1;i<=n;i++){
		scanf("%d%d%d",&a[i].c,&a[i].p,&a[i].d);
		a[i].dp=a[i].p*a[i].d;
	} 
	sort(a+1,a+1+n,cmp);
	int k=0;
	f[0][1]=a[1].dp;
	for(int i=1;i<=n;i++){
		if(k==0){
			f[k+1][i]=min(f[k][i],f[k][i-1]+a[i].p*(a[i].c+a[i].d*(i-1)));
			k=1;
		}
		else if(k==1){
			f[k-1][i]=min(f[k][i],f[k][i-1]+a[i].p*(a[i].c+a[i].d*(i-1)));
			k=0;
		}
	}
	int ans=0;
	if(k==1){
		for(int i=1;i<=n;i++){
			if(f[1][i]<=s)ans++;
		}
	}
	if(k==0){
		for(int i=1;i<=n;i++){
			if(f[0][i]<=s)ans++;
		}
	}
	cout<<ans;
	return 0;
}