Bessie has gone to the mall‘s jewelry store and spies a charm bracelet. Of course, she‘d like to fill it with the best charms possible from the N (1 ≤ N ≤ 3,402) available charms. Each charm i in the supplied list has a weight W_i (1 ≤ W_i ≤ 400), a ‘desirability‘ factor D_i (1 ≤ D_i ≤ 100), and can be used at most once. Bessie can only support a charm bracelet whose weight is no more than M (1 ≤ M ≤ 12,880).

Given that weight limit as a constraint and a list of the charms with their weights and desirability rating, deduce the maximum possible sum of ratings.

 1 #include <iostream> 2 #include <algorithm> 3 #include <cstring> 4 using namespace std; 5  6 const int MAX_N=3500; 7 const int MAX_M=13000; 8  9 int v[MAX_N],w[MAX_N];10 int f[MAX_M];11 int main()12 {13     int N,M,V,W;14     while(scanf("%d%d",&N,&M)==2){15         memset(f,0,sizeof(f));16         for(int i=1;i<=N;i++){17             scanf("%d%d",&V,&W);18             for(int j=M;j>=0;j--)19                 if(j>=V) f[j]=max(f[j], f[j-V]+W);20         }21         printf("%d\n",f[M]);22     }23 }