#include <fstream>
#include <algorithm>

using namespace std;

int g[5001], v[5001], n, G;
int a[10001], b[10001];

// best[i][j] = val max obtinuta din primele i obiecte
// obttinand greutatea j
// best[i][j] = best[i-1][j], daca obiectul i nu s-a ales
//              best[i-1][j - g[i]] + v[i], daca am ales obiectul i

void Citire()
{
    int i;
    ifstream fin("rucsac.in");
    fin >> n >> G;
    for (i = 1; i <= n; i++)
        fin >> g[i] >> v[i];
}

void Rezolvare()
{
    int pas, j, maxim;
    a[g[1]] = v[1];
    for (pas = 2; pas <= n; pas++)
    {
        b[j] = a[j];
        for (j = 0; j <= G; j++)
           if (g[pas] <= j)
              b[j] = max(b[j], a[j - g[pas]] + v[pas]);
        for (j = 0; j <= G; j++)
            a[j] = b[j];
    }
    maxim = a[1];
    for (j = 1; j <= G; j++)
        maxim = max(maxim, a[j]);
    ofstream fout("rucsac.out");
    fout << maxim << "\n";
    fout.close();
}

int main()
{
    Citire();
    Rezolvare();
    return 0;
}