1 #include <bits/stdc++.h>
 2 using namespace std;
 3 int w[15000],d[15000],dp[15000];
 4 int main()
 5 {
 6     int n,m;
 7     freopen("charm.in","r",stdin);
 8     freopen("charm.out","w",stdout);
 9     scanf("%d%d",&n,&m);
10     for(int i=1;i<=n;i++)
11         scanf("%d%d",&w[i],&d[i]);
12     for(int i=1;i<=n;i++)
13         for(int j=m;j>=w[i];j--)
14             dp[j]=max(dp[j],dp[j-w[i]]+d[i]);
15     cout<<dp[m]<<endl;
16     return 0;
17 }