#include <stdio.h>

using namespace std;
FILE *f,*g;
int gr[10002],p[10002],cost[3][10002];
int main()
{
    int G,n,lp=1,lc=0,i,j;
    f=fopen("rucsac.in","r");
    g=fopen("rucsac.out","w");
    fscanf(f,"%d %d",&n,&G);
    for(i=1;i<=n;i++)
        fscanf(f,"%d %d",&gr[i],&p[i]);
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=G;j++)
        {
            if(gr[i]<=j)
            {
                if(p[i]+cost[lp][j-gr[i]]>cost[lp][j])
                    cost[lc][j]=p[i]+cost[lp][j-gr[i]];
                else
                    cost[lc][j]=cost[lp][j];
            }
            else
               cost[lc][j]=cost[lp][j];
        }
        lc=1-lc;
        lp=1-lp;
    }
    /*for(i=0;i<=1;i++)
    {
        for(j=1;j<=G;j++)
            fprintf(g,"%d ",cost[i][j]);
        fprintf(g,"\n");
    }*/
    fprintf(g,"%d\n",cost[lp][G]);
    fclose(f);
    fclose(g);
    return 0;
}