#include <fstream>
#define MX 5001
using namespace std;

ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
int n,g;
int w[MX],p[MX];
int d[2][10001];

int maxim(int a, int b)
{
    if(a > b) return a;
    return b;
}

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=0; j<=g; j++)
        {
            if(j < w[i]) d[i%2][j] = d[(i+1)%2][j];
            else d[i%2][j] = maxim(d[ (i+1)%2 ][j],
                                   d[ (i+1)%2 ][j-w[i]] + p[i]);
        }
    }
}

int main()
{
    citire();
    rucsac();
    fout<<d[n%2][g];

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