#include <stdio.h>
#define G 10010
#define N 5010

int a[2][G],v[N],n,g,m[N],i,j,k;

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",m+i,v+i);
	for (i=1; i<=n; i++) {
		for (j=1; j<=g; j++) {
			a[k][j]=a[1-k][j];
			if (j-m[i]>=0)
				if (a[1-k][j-m[i]]+v[i]>a[k][j])
					a[k][j]=a[1-k][j-m[i]]+v[i];
		}
		k=1-k;
	}
	printf ("%d\n",a[1-k][g]);
    return 0;
}