/* 
 * File:   main.c
 * Author: Vladutz
 *
 * Created on March 2, 2012, 3:42 PM
 */

#include <stdio.h>

/*
 * 
 */
int n,G,g[5002],c[5002],v[10003],i,s,sol;
FILE *f,*h;
int main(int argc, char** argv) 
{
    f=fopen("rucsac.in","r");
    h=fopen("rucsac.out","w");
    fscanf(f,"%d%d",&n,&G);
    for(i=1;i<=n;i++)
        fscanf(f,"%d%d",&g[i],&c[i]);
    for(i=1;i<=n;i++)
        for(s=G-g[i];s>=0;s--)
            if(v[s+g[i]] < v[s] + c[i])
            {
                v[s+g[i]]=v[s]+c[i];
                if(v[s+g[i]]>sol)
                    sol=v[s+g[i]];
            }
    fprintf(h,"%d",sol);
    fclose(f);
    fclose(h);
    return 0;
}