#include <fstream>
using namespace std;
ofstream fout("rucsac.out");
ifstream fin ("rucsac.in");
int v[11001],val[5005],greut[5005],i,j,maxim,g,n;
int main()
{
    fin>>n>>g;
    for( i = 1 ; i <= n ; i++)
    {
        fin>>greut[ i ]>>val[ i ];
    }
    maxim = greut[ 1 ];
    v[ maxim ] = val[ 1 ] ;
    for( i = 2 ; i <= n ; i++)
    {
        for( j = maxim + greut[ i ] ; j > greut[ i ] ; j-- )
        {
            if(v[ j - greut[ i ] ])
            {
                v[ j ] = max( v[ j ] , v[ j - greut[ i ] ] + val [ i ] );
            }
        }
        maxim = maxim + greut[ i ];
    }
    for( i = 1 ; i <= g ; i++) maxim = max(maxim,v[ i ]);
    fout<<maxim;
}