#include <bits/stdc++.h>

using namespace std;

ifstream fin("rucsac.in");
ofstream fout("rucsac.out");

#define cin fin
#define cout fout

#define DIM 5005
#define oo 2000000005

int n,g,w[DIM],p[DIM],dp[10001],ans;


int main()
{
    cin>>n>>g;
    for(int i=1;i<=n;i++) cin>>w[i]>>p[i];
    ans=0; dp[0]=0;
    for(int i=1;i<=n;i++)
    {
		for(int j=g-w[i];j>=0;j--)
        {
			if( dp[j+w[i]]<dp[j]+p[i])
			{
				dp[j+w[i]]=dp[j]+p[i];
				if( dp[j+w[i]]>ans)
					ans=dp[j+w[i]];
			}
		}
    }
    cout<<ans;
    return 0;
}