#include <fstream>
#define NMAX 5005
#define GMAX 10005

using namespace std;

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

struct A
{
    int greutate, val;
};

A v[NMAX];
int dp[3][GMAX];

int main()
{
    int n, g, i, j;

    fin >> n >> g;
    for ( i = 1 ; i <= n ; i++ ) fin >> v[i].greutate >> v[i].val;

    for ( i = v[1].greutate ; i <= g ; i++ ) dp[1][i] = v[1].val;
    for ( i = 2 ; i <= n ; i++ )
    {
        for ( j = 1 ; j < v[i].greutate ; j++ ) dp[2][j] = dp[1][j];
        for ( j = v[i].greutate ; j <= g ; j++ ) dp[2][j] = max ( dp[1][j], dp[1][j-v[i].greutate] + v[i].val );

        for ( j = v[i].greutate ; j <= g ; j++ ) dp[1][j] = dp[2][j];
    }

    fout << dp[2][g];

    return 0;
}