DP(背包問題)

/************************************************************/

#include<stdio.h>                 
#include<stdlib.h>     
main()     
{     
 int n,a,b,m;  
 while(scanf("%d %d",&n,&m)==2)  
  {  
   int value[50000]={0},max=0,sum=n*m;  
   for(a=0;a<m;a++)  
    {  
     int w1,w,price1;  
     scanf("%d %d",&w1,&price1);
     for(b=n-w1;b>=0;b--) 
      {  
       if(value[b+w1]<value[b]+price1*w1)
        {  
         value[b+w1]=value[b]+price1*w1;  
         if(value[b+w1]>max)  
          max=value[b+w1];  
        }  
      }
    }  
    printf("%d\n",max);  
  }  
 return 0;     
}