#include <fstream>
#include <stdio.h>

#define MAXN 5012
#define MAXG 10012

FILE *fin, *fout;

using namespace std;

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

int n, g;
int castig[MAXN][MAXG];
int p[MAXN], gr[MAXN];

inline void Read()
{
   // fin >> n >> g;

    fscanf(fin, "%d %d", &n, &g);

    for (int i = 1; i <= n; i++)
    {
       // fin >> gr[i] >> p[i];
       fscanf(fin, "%d %d", &gr[i], &p[i]);
    }
}

inline void Solve()
{
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= g; j++)
        {
            if (j - gr[i] >= 0)
            {
                if (castig[i - 1][j - gr[i]] + p[i] > castig[i - 1][j])
                    castig[i][j] = castig[i - 1][j - gr[i]] + p[i];
                else castig[i][j] = castig[i - 1][j];
            }
            else
                castig[i][j] = castig[i - 1][j];
        }
    }

    //fout << castig[n][g];
    fprintf(fout, "%d", castig[n][g]);
}

int main ()
{
    fin = fopen("rucsac.in", "r");
    fout = fopen("rucsac.out", "w");

    Read();
    Solve();

   // fin.close(); fout.close(); return 0;
   fclose(fin); fclose(fout); return 0;
}