1 #include<iostream> 2 #include<memory.h> 3 using namespace std; 4 #define maxn 505 5 #define maxm 100005 6 int need[maxn],value[maxn]; 7 int dp[maxm]; 8 int main() 9 {10     int n,m;11     while(cin>>n>>m)12     {13         memset(dp,0,sizeof(dp));14         for(int i = 1; i <= n; i++)15             cin>>need[i]>>value[i];16         for(int j = 0; j <= m; j++)17             dp[j] = 0;18         for(int i = 1; i <= n; i++)19             for(int j = m; j >= need[i]; j--)20                 dp[j] = max(dp[j],dp[j - need[i]] + value[i]);21         cout<<dp[m]<<endl;22     }23     return 0;24 }