#include <fstream>

using namespace std;

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

const int Nmax=5002;
const int Gmax=10002;

int n,g;
int w[Nmax],p[Nmax],d[Nmax][Gmax];

int maxim ( int x , int y ){
    return x > y ? x : y;
}

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

    for ( int i=1 ; i<=n ; i++ ){
        for ( int j=1 ; j<=g ; j++ ){
            if ( w[i] <= j)
                d[i][j]=maxim( d[i-1][j] , d[i-1][j-w[i]]+p[i] );
        }
    }

    fout<<d[n][g];
}