#include<stdio.h>
struct obiect {int x,y;} a[5001];
int v[2][10001];
int main(){
	int k,i,n,m,j;
	freopen("rucsac.in","r",stdin);
	freopen("rucsac.out","w",stdout);
	scanf("%d",&n);
	scanf("%d",&m);
	for(i=1;i<=n;i++)
        scanf("%d%d",&a[i].x,&a[i].y);

	for(i=1;i<=n;i++){
		for(j=1;j<=m;j++)
		{
		    if(j-a[i].x>=0){
                k=v[0][j-a[i].x]+a[i].y;
                    if(v[0][j]>=k)
                        v[1][j]=v[0][j];
                    else
                        v[1][j]=k;
            }
            else
                v[1][j]=v[0][j];
        }
        for(j=1;j<=m;j++)
            v[0][j]=v[1][j];
	}
	printf("%d ",v[1][m]);
	return 0;
}