#include <fstream>

using namespace std;

const int NMAX= 5000, GMAX= 10000;

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

int dp[GMAX+4];
int W[NMAX+4], P[NMAX+4];

int main(  )
{
    int N, G;
    in >> N >> G;

    for( int i= 1; i<=N; ++i )
    {
        in >> W[i] >> P[i];
    }

    dp[0]= 0;
    int ans= 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] ];
                }
            }
        }
    }

    out << ans << '\n';

    return 0;
}