#include <fstream>
#include <algorithm>
using namespace std;

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

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

int main()
{

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

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