#include <fstream>
#define MaxN 5001
#define MaxG 10001
using namespace std;

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

void Read();
void Write();
void Knapsack();

int c[2][MaxG];
int w[MaxN], p[MaxN];
int n, g, l;

int main()
{
    Read();
    Knapsack();
    Write();

    is.close();
    os.close();
    return 0;
}

void Read()
{
    is >> n >> g;
    for ( int i = 1; i <= n; ++i )
        is >> w[i] >> p[i];
}

void Write()
{
    os << c[l][g] << '\n';
}

void Knapsack()
{
    for ( int i = 1; i <= n; ++i, l = !l )
        for ( int j = 0; j <= g; ++j )
        {
            c[!l][j] = c[l][j];
            if ( j >= w[i] )
            {
                c[!l][j] = max(c[!l][j], c[l][j - w[i]] + p[i]);
            }
        }
}