#include <fstream>
using namespace std;
#define IN "rucsac.in"
#define OUT "rucsac.out"
#define NMAX 5001
#define GMAX 10001

int N,G;
int g[NMAX],p[NMAX];
int sol[GMAX];
int maxim,i,j;

int main() {

    ifstream fin(IN);
    ofstream fout(OUT);

    fin>>N>>G;
    for(i=1;i<=N;i++)
        fin>>g[i]>>p[i];

    for(i=1;i<=N;i++)
    {
        for(j=G-g[i];j>=0;j--)
        {
            if(sol[j+g[i]]<sol[j]+p[i])
            {
                sol[j+g[i]]=sol[j]+p[i];
                if(sol[j+g[i]]>maxim)
                    maxim=sol[j+g[i]];
            }
        }
    }

    fout<<maxim<<'\n';
    return 0;
}