https://www.luogu.com.cn/problem/P1833

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cctype>
#include<string>
#include<cstring>
#include<algorithm>
using namespace std;
inline int read(){
	int f=1,num=0;
	char rd=getchar();
	while(!isdigit(rd)){
		if(rd=='-') f=-1;
		rd=getchar();
	}
	while(isdigit(rd)){
		num=num*10+rd-48;
		rd=getchar();
	}
	return f*num;
}
int dp[1200];
int main()
{
	int m=read()*60+read()-read()*60-read();m=-m;
	int n=read(),w[12000],c[12000],p[12000];
	for(int i=1;i<=n;i++) w[i]=read(),c[i]=read(),p[i]=read();
	for(int i=1;i<=n;i++){
		if(p[i]==0){
			for(int j=w[i];j<=m;j++){
				dp[j]=max(dp[j],dp[j-w[i]]+c[i]);
			}
		}
		else{
			int x=p[i],now=1;
			while(now<=x){		
				int a=now*w[i],b=now*c[i];
				if(a>m) break;
				for(int j=m;j>=a;j--){
					dp[j]=max(dp[j],dp[j-a]+b);
				}
				x-=now;
				now<<=1;
			}
			if(x>0){
				int a=x*w[i],b=x*c[i];
				for(int j=m;j>=a;j--){
					dp[j]=max(dp[j],dp[j-a]+b);
				}
			}
		}
	}
	return printf("%d\n",dp[m])&0;
}