#include <fstream>
using namespace std;

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

const int MaxN = 100;
const int MaxG = 1000;

int g[MaxN], v[MaxN];
int n, G;
int c[MaxN][MaxG]; // PD 2D
// c[i][j] - val max a obiectelor alese din intervalul [1..i] care nu depasesc
// valoare totala j

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];
        }
    }

}