#include <stdio.h>

int w[5001],p[5001];
long int d[1][10001];

void main(void){
     freopen("rucsac.in","r",stdin);
     freopen("rucsac.out","w",stdout);
     int n,i,j,k,g;
     scanf("%d%d",&n,&g);
     for (i=1;i<=n;i++) scanf("%d%d",&w[i],&p[i]);
     i=0;
     for (k=1;k<=n;k++){
         i=1-i;
         for (j=0;j<=g;j++){
             d[i][j]=d[1-i][j];
             if (j>=w[k])
                if (p[k]+d[1-i][j-w[k]]>d[i][j]) d[i][j]=p[k]+d[1-i][j-w[k]];
             }
             }
     printf("%d",d[i][g]);             
     }