#include<algorithm>
#include<cstdio>
int T,n,i,j,v[110],w[110],f[1010];
int main(){
scanf("%d%d",&T,&n);
for(i=1;i<=n;i++)
scanf("%d%d",&v[i],&w[i]);
for(i=1;i<=n;i++)
for(j=T;j>=v[i];j--)
f[j]=std::max(f[j],f[j-v[i]]+w[i]);
printf("%d",f[T]);
return 0;
}
#include<algorithm>
#include<cstdio>
using namespace std;
int tmp,T1,T2,x,y,n,i,j,k,v1[105],v2[105],w[105],dp[105][105],ans[105][105];
int main(){
scanf("%d",&n);
for(i=1;i<=n;i++)scanf("%d%d%d",&v1[i],&v2[i],&w[i]);
scanf("%d%d",&T1,&T2);
for(i=1;i<=n;++i)
for(j=T1;j>=v1[i];--j)
for(k=T2;k>=v2[i];--k){
if(dp[j][k]<(tmp=dp[j-v1[i]][k-v2[i]]+1)){
dp[j][k]=tmp;
ans[j][k]=ans[j-v1[i]][k-v2[i]]+w[i];
}
else if(dp[j][k]==tmp)ans[j][k]=min(ans[j][k],ans[j-v1[i]][k-v2[i]]+w[i]);
}
printf("%d",ans[T1][T2]);
}
#include<algorithm>
#include<cstdio>
using namespace std;
int T,n,i,j,a[65],s,t,r1,r2,r[65][3],v[65],w[65],f[32010];
int main(){
scanf("%d%d",&T,&n);
v[0]=0xfffffff;
for(i=1;i<=n;i++){
scanf("%d%d%d",&v[i],&s,&a[i]);
if(a[i])r[a[i]][++r[a[i]][0]]=i;w[i]=v[i]*s;
}
for(i=1;i<=n;i++)
for(j=T;j>=v[i]&&(!a[i]);j--){
t=j-v[i],r1=r[i][1],r2=r[i][2];
f[j]=max(f[j],f[t]+w[i]);
if(v[r1]<=t)f[j]=max(f[j],f[t-v[r1]]+w[i]+w[r1]);
if(v[r2]<=t)f[j]=max(f[j],f[t-v[r2]]+w[i]+w[r2]);
if(v[r1]+v[r2]<=t)f[j]=max(f[j],f[t-v[r1]-v[r2]]+w[i]+w[r1]+w[r2]);
}
printf("%d",f[T]);
}
#include<algorithm>
#include<cstring>
#include<cstdio>
int ans,T,n,i,j,k,K,a,b,t,re[45],v[210],w[210],f[5010][45];
int main(){
scanf("%d%d%d",&K,&T,&n);
memset(f,-127,sizeof(f));f[0][1]=0;
for(i=1;i<=n;i++)
scanf("%d%d",&v[i],&w[i]);
for(i=1;i<=n;i++)
for(j=T;j>=v[i];j--){
a=b=1,t=0;
while(t<=K){
if(f[j][a]>=f[j-v[i]][b]+w[i])re[++t]=f[j][a++];
else re[++t]=f[j-v[i]][b++]+w[i];
}
for(k=1;k<=K;k++)f[j][k]=re[k];
}
for(i=1;i<=K;i++)ans+=f[T][i];
printf("%d",ans);
return 0;
}
#include<algorithm>
#include<cstring>
#include<cstdio>
#define Re register int
using namespace std;
const int N=103,M=4e4+3;
int n,m,x,y,z,V,ans,v[N*17],w[N*17],dp[M];
inline void in(Re &x){
Re fu=0;x=0;char ch=getchar();
while(ch<'0'||ch>'9')fu|=ch=='-',ch=getchar();
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
x=fu?-x:x;
}
int main(){
in(m),in(V);
memset(dp,-127,sizeof(dp));
dp[0]=0;
while(m--){
in(x),in(y),in(z);Re p=1;
while(z>=p)v[++n]=y*p,w[n]=x*p,z-=p,p<<=1;
if(z)v[++n]=y*z,w[n]=x*z;
}
for(Re i=1;i<=n;++i)
for(Re j=V;j>=v[i];--j)
dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
for(Re i=0;i<=V;++i)ans=max(ans,dp[i]);
printf("%d\n",ans);
}
#include<bits/stdc++.h>
using namespace std;
int T,n,ans,a[105],dp[30005];
int main(){
scanf("%d",&T);
while(T--){
memset(dp,-127,sizeof(dp));
scanf("%d",&n);dp[0]=ans=0;
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
for(int i=1;i<=n;i++)
for(int j=a[i];j<=25000;j++)
dp[j]=max(dp[j],dp[j-a[i]]+1);
for(int i=1;i<=n;++i)ans+=dp[a[i]]==1;
printf("%d\n",ans);
}
}
#include<algorithm>
#include<cstdio>
using namespace std;
int x,a,b,c,d,T,n,i,j,t,f[1010],v[100010],w[100010];
int main(){
scanf("%d:%d%d:%d%d",&a,&b,&c,&d,&n);
T=c*60+d-a*60-b;
for(i=1;i<=n;i++){
scanf("%d%d%d",&a,&b,&c);
if(!c){
for(j=0;j+a<=T;j++)
f[j+a]=max(f[j+a],f[j]+b);
continue;
}
x=1;
while(c>=x){v[++t]=x*a,w[t]=x*b,c-=x,x<<=1;}
v[++t]=c*a,w[t]=c*b;
}
for(i=1;i<=t;i++)
for(j=T;j>=v[i];j--)
f[j]=max(f[j],f[j-v[i]]+w[i]);
printf("%d",f[T]);
return 0;
}