#include <stdio.h>
#define MAXN 5010
#define MAXG 10010
int max(int a,int b)
{
    if(a>b)
        return a;
    return b;
}
int n,g,pmax,c,i;
int w[MAXN],p[MAXN];
int d[2][MAXG];
int main()
{
    freopen("rucsac.in","r",stdin);
    freopen("rucsac.out","w",stdout);
    scanf("%d%d",&n,&g);
    for(i=1;i<=n;++i)
        scanf("%d%d",&w[i],&p[i]);
    int l=0;
    for(i=1;i<=n;++i,l=1-l)
        for(c=0;c<=g;++c){
            d[1-l][c]=d[l][c];
             if(w[i]<=c)
                d[1-l][c]=max(d[1-l][c],d[l][c-w[i]]+p[i]);
        }
    pmax=d[l][g];
    printf("%d\n",pmax);
    return 0;
}