#include <fstream>
using namespace std;

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

//avem c[v][i] = castigul maxim obtinut daca alegem din primele k obiecte, cu greutatea totala cel mult i

int main()
{
    int c[2][10001] = {};
    int l;
    int i, n, g[5001], v[5001], gmax, j;
    fin >> n >> gmax;
    for (i = 1; i<=n; i++)
        fin >> g[i] >> v[i];
    l = 0;
    for (i = 1; i<=n; i++, l = 1-l)
    {
        for (j = 1; j<g[i]; j++)
            c[l][j] = c[1-l][j];
        for (j = g[i]; j<=gmax; j++)
            c[l][j] = max(c[1-l][j], v[i] + c[1-l][j-g[i]]);
    }
    fout << c[1-l][gmax];
    return 0;
}