#include <fstream>
#include <algorithm>
#define max(a,b)    (a>b ? a:b)
using namespace std;

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


int n, g;
int s[5000], v[5000];
int d[3][5000];

int main()
{

    is >> n >> g;
    for ( int i = 1; i <= n; ++i )
    is >> s[i] >> v[i];

    int f = 0;

    for ( int i = 1; i <= n; ++i )
    {

        for ( int j = 0; j <= g; ++j )
        {
            d[1-f][j] = d[f][j];
            if ( s[i] <= j )
            {
                d[1-f][j] = max(d[1-f][j], d[f][j-s[i]]+v[i] );
            }
        }
                f = 1-f;
    }
    os << d[f][g];
    return 0;
}