1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# include <iostream>
# include <string.h>
using namespace std;
int dp[100010];
int main()
{
    int n,m,w,v,i,j;
    while(cin>>n>>m)
    {
        memset(dp,0,sizeof(dp));
        for(i=1;i<=n;i++)
        {
            cin>>w>>v;
            for(j=m;j>=w;j--)
                dp[j]=dp[j]>dp[j-w]+v?dp[j]:dp[j-w]+v;
        }
        cout<<dp[m];
    }
    return 0;
}
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX