#include <bits/stdc++.h>
#define DimMax 5000
#define ValMax 10000
#define LinMax 2

using namespace std;

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

int n, G;
int w[DimMax + 1], p[DimMax + 1];
int dp[LinMax][ValMax + 1];
int l;

int main()
{
    fin >> n >> G;
    for ( int i = 1; i <= n; i++ )
        fin >> w[i] >> p[i];

    for ( int i = 1; i <= n; i++,l = 1 - l )
        for ( int j = 0; j <= G; j++ )
        {
            dp[l][j] = dp[l - 1][j];
            if ( w[i] <= j )
            dp[l][j] = max(dp[1 - l][j], dp[1 - l][j - w[i]] + p[i]);
        }
    fout << dp[l][G];
    return 0;
}