https://www.luogu.com.cn/record/179027305
rt

#include<bits/stdc++.h>
using namespace std;
int h1,m1,h2,m2,t,n,w[10002],v[10002],p[10002],w1[102],v1[102];
int dp[1440];
int main(){
	scanf("%d:%d",&h1,&m1);
	scanf("%d:%d",&h2,&m2);
	t=(h2-h1)*60+m2-m1;
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>w[i]>>v[i]>>p[i];
	for(int i=1;i<=n;i++){
		if(p[i]==0)
			for(int j=w[i];j<=t;j++)
				dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
		else if(p[i]==1)
			for(int j=t;j>=w[i];j--)
			    dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
		else{
			int bk=p[i];
			int cnt=1,bn=1;
			while(bk){
				if(bk>=bn){
					bk-=bn;
					w1[cnt]=w[i]*bn;
					v1[cnt]=v[i]*bn;
					bn*=2;
					cnt++;
				}
				else{
					w1[cnt]=w[i]*bk;
					v1[cnt]=v[i]*bk;
					bk=0;
				}
			}
			for(int j=1;j<=cnt;j++)
				for(int k=t;k>=w1[i];k--)
					dp[k]=max(dp[k],dp[k-w1[i]]+v1[i]);
       }
	}
	cout<<dp[t];
	return 0;
}