#include<bits/stdc++.h>
#define maxn 5001
#define maxg 10001

using namespace std;

int w[maxn],p[maxn];
int opt[maxg];
FILE *fin=fopen("rucsac.in","r");
FILE *fout=fopen("rucsac.out","w");
int main()
{

    int N,G,sol;
    fscanf(fin,"%d %d",&N,&G);

    for(int i=1;i<=N;++i)
        fscanf(fin,"%d %d",&w[i],&p[i]);

    sol=0;

    for(int i=1;i<=N;++i)
        for(int j=G-w[i];j>=0;--j)
            if(opt[w[i]+j]<opt[j]+p[i])
        {
            opt[w[i]+j]=opt[j]+p[i];
            if(opt[w[i]+j]>sol)
                sol=opt[w[i]+j];
        }
    fprintf(fout,"%d",sol);
    return 0;
}