#include <fstream>
using namespace std;

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

int c[5001][10001]; //c[i][j] = vmax a unor obiecte din interv 1, i
                 // a caror greutate toala sa nu depaseasca j

int n, G, v[5001], g[5001];

void ReaD();
void Knapsack_2D();

int main()
{
    ReaD();
    Knapsack_2D();

    os << c[n][G];

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

void ReaD()
{
    is >> n >> G;
    for( int i = 1; i <= n; ++i )
    {
        is >> g[i];
        is >> v[i];
    }
}

void Knapsack_2D()
{
    for( int i = 1; i <= n; ++i )
        for( int j = 1; j <= G; ++j )
        {
            c[i][j] = c[i-1][j];
            if( j >= g[i] && c[i][j] < c[i-1][j-g[i]] + v[i] )
                c[i][j] = c[i-1][j-g[i]] + v[i];
        }





}