1 #include<stdio.h> 2 #include<string.h> 3 4 int main() 5 { 6 int i,j,f[100],t[1000],w[100],T,M; 7 scanf("%d%d",&T,&M); 8 for(i=0;i<M;i++) 9 scanf("%d%d",&t[i],&w[i]); 10 memset(f,0,sizeof(f)); 11 for(i=0;i<M;i++) 12 for(j=T;j>=t[i];j--) 13 f[j]=f[j]>f[j-t[i]]+w[i]?f[j]:f[j-t[i]]+w[i]; 14 printf("%d\n",f[T]); 15 return 0; 16 }