Rucsac2

#include <iostream>
#include <cstring>
using namespace std;
int n,G,g[1001],v[1001];

int rucsac(int G,int n,int g[],int v[])
{
    int dp[G+1];
    memset(dp,0,sizeof dp);
    for(int i=0;i<=G;++i)
      for(int j=0;j<n;++j)
         if (g[j]<=i)
            dp[i]=max(dp[i],dp[i-g[j]]+v[j]);
    return dp[G];
}

int main ()
{
    cin>>n>>G;
    for(int i=0;i<n;++i)
        cin>>g[i]>>v[i];
    cout<<rucsac(G,n,g,v);
    return 0;
}