#include <bits/stdc++.h>
#define NMAX 5001
#define NMAXG 10010
using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
int w[NMAX],p[NMAX];
int N,G;
int D[2][NMAXG];
int main()
{
    int i,cw;
    fin>>N>>G;
    for(i=1;i<=N;++i)
    {
        fin>>w[i]>>p[i];
    }
    int l=0;
    for(i=1;i<=N;++i,l=1-l)
    {
        for(cw=0;cw<=G;++cw)
        {
            D[1-l][cw]=D[l][cw];
            if(w[i]<=cw)
            D[1-l][cw]=max(D[1-l][cw],D[l][cw-w[i]]+p[i]);
        }
    }
    int Pmax=D[l][G];
    fout<<Pmax;
    return 0;
}