#include <fstream>
#define NMax 5001
#define GMax 10001

using namespace std;

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

int p[NMax], w[NMax], a[GMax], b[GMax], n, g;

void Citire()
{
    int i;
    fin >> n >> g;
    for (i = 1; i <= n; ++ i)
        fin >> w[i] >> p[i];
}

void Rucsac()
{
    int i, j;
    for (i = 1; i <= n; ++ i)
        {
         for (j = 1; j <= g; ++ j)
            {
             if (w[i] > j) a[j] = b[j];
             else
                a[j] = max(b[j], b[j - w[i]] + p[i]);
            }
         for (j = 1; j <= g; ++ j)
            b[j] = a[j];
        }
}

int main()
{
    Citire();
    fin.close();
    Rucsac();
    fout << b[g] << "\n";
    fout.close();
    return 0;
}