1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <iostream>
using namespace std;
int main()
{
    int i,j,n,m;  
    int w[505],v[505],bag[100050]={0}; 
//  memset(bag,0,sizeof(bag));
    cin>>n>>m;
    for(i=1; i<=n; i++)
      cin>>w[i]>>v[i];
    for(i=1; i<=n; i++)
    {
        for(j=m; j>=w[i]; j--)
        {
            if(bag[j-w[i]]+v[i]>bag[j])
            {
                 bag[j] = bag[j-w[i]]+v[i];
            }
        }
    }
    cout<<bag[m]<<endl;
    return 0;
}
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX