#include <stdio.h>
#define nMax 5001
#define gMax 10001
int g[nMax],c[nMax],n,gt;
void read()
{ int i;
scanf("%d %d\n",&n,&gt);
for(i=1;i<=n;++i)
    scanf("%d %d\n",&g[i],&c[i]);
}
void solve()
{ int x,y,i,j;
  int d[2][gMax];
for(i=1;i<=n;++i)
    { if(i%2!=0){x=0; y=1;}
        else {x=1; y=0;}
    d[y][0]=0;
    for(j=1;j<=gt;++j)
        {   d[y][j]=d[x][j];
            if(j-g[i]>=0&&d[y][j]<d[x][j-g[i]]+c[i])d[y][j]=d[x][j-g[i]]+c[i];
        }
    }
if(n%2!=0)printf("%d",d[1][gt]);
else printf("%d",d[0][gt]);
}
int main()
{
freopen("rucsac.in","r",stdin);
freopen("rucsac.out","w",stdout);
read();
solve();
fclose(stdin);
fclose(stdout);
return 0;
}