#include <fstream>
using namespace std;

#define MAXN 10000
#define MAXG 10000

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

int c[2][MAXG];
int lp, lc = 1;
int n, S, g[MAXG], v[MAXN];

int main()
{
    is >> n >> S;
    for ( int i = 1; i <= n; i++ )
        is >> g[i] >> v[i];
    for( int i = 1; i <= n; ++i, lc = !lc, lp =! lp )
    {
        for( int j = 1; j <= S; ++j )
        {
            c[lc][j] = c[lp][j];
            if( j >= g[i] && c[lc][j] < c[lp][j-g[i]] + v[i] )
                c[lc][j] = c[lp][j-g[i]] + v[i];
        }
    }
    os << c[lp][S];
    is.close();
    os.close();
    return 0;
}