#include<fstream>
using namespace std;
ifstream f("rucsac.in");
ofstream g("rucsac.out");
int N,G,w[5001],v[5001],dp[10001],Max;
int main()
{
    f>>N>>G;
    for(int i=1;i<=N;++i)f>>w[i]>>v[i];
    for(int i=1;i<=N;++i)
        for(int j=G-w[i];j>=0;--j)
            if(dp[j+w[i]]<dp[j]+v[i])
                dp[j+w[i]]=dp[j]+v[i],Max=max(Max,dp[j+w[i]]);
    g<<Max;
    return 0;
}