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

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

int n , G;
int v[10001] , g[10001] ;
int sol[100001] , amax;

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

    for ( int i = 1; i <= n ; i++ )
        for ( int j = G-g[i] ; j >=0 ; j-- )
        {
            if ( sol[j+g[i]] < sol[j] + v[i])
            {
                sol[j+g[i]] = sol[j] + v[i];
                if ( sol[j+g[i]] > amax )
                    amax = sol[j+g[i]];
            }
        }
    fout << amax;
    return 0;
}