#include <fstream>
#include <cstring>
#define inf -1000001
using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
int n,g,w[5002],p[5002];
int d[10002],maxim=inf,i,j;
int main(){
    fin>>n>>g;
    for(i=1;i<=n;i++)
        fin>>w[i]>>p[i];
    memset(d,inf,sizeof(d));
    d[0]=0;
    for(i=1;i<=n;i++){
        for(j=g;j>=0;j--)
            if(d[j]!=inf)
                if(j+w[i]<=g){
                    d[j+w[i]]=max(d[j+w[i]],d[j]+p[i]);
                    if(d[j+w[i]]>maxim)
                        maxim=d[j+w[i]];
                }
    }
    fout<<maxim;
    fin.close();fout.close();
    return 0;
}