/* 
 * 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,a[10003][5002],j;
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<=G;i++)
        v[i]=-1;
    for(s=1;s<=G;s++)
        for(i=1;i<=n;i++)
            if(g[i]<=s && a[s-g[i]][i]==0 && v[s-g[i]]!=-1)
                if(v[s]<v[s-g[i]] + c[i])
                {
                    v[s]=v[s-g[i]] + c[i];
                    for(j=1;j<=n;j++)
                        a[s][j]=a[s-g[i]][j];
                    a[s][i]=1;
                }
    fprintf(h,"%d",v[G]);
    fclose(f);
    fclose(h);
    return 0;
}