#include <fstream>

using namespace std;

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

int a[2][10001], w[5001], p[5001], G, n;

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

void Calc()
{
    int i, j, mod;
    mod=1;
    for(i=1; i<=n; i++)
    {
        mod=1-mod;
        for(j=1; j<=G; j++)
        {
            if(w[i]>j) a[mod][j]=a[1-mod][j];
            else a[mod][j]=max(a[1-mod][j], a[1-mod][j-w[i]]+p[i]);
        }
    }
    fout<<a[mod][G];
}

int main()
{
    Citire();
    Calc();
    fin.close();
    fout.close();
    return 0;
}