#include <iostream>
#include <fstream>

using namespace std;

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

int a[10001];

struct cel
{
    int g, p;
}v[5001];

int main()
{
    int n, g;
    f >> n >> g;
    for ( int i = 1; i <= n; i ++ )
        f >> v[i].g >> v[i].p;
    for ( int i = 1; i <= n; i ++ )
        for ( int j = g; j >= v[i].g; j -- )
            a[j] = max ( a[j], a[ j - v[i].g] + v[i].p );

    for ( int i = g; i > 0; i -- )
        if ( a[i] > 0 )
        {
            gf << a[i];
            return 0;
        }
    return 0;
}