#include<cstdio>
using namespace std;
int n,gr,grt[5010],p[5010],a[2][10010],i,j;
int maxim(int a,int b)
{
	if(a<b)
	{
		return b;
	}
	else
	{
		return a;
	}
}
int main()
{
	freopen("rucsac.in","r",stdin);
	freopen("rucsac.out","w",stdout);
	scanf("%d%d",&n,&gr);
	for(i=1;i<=n;i++)
	{
		scanf("%d%d",&grt[i],&p[i]);
	}
	for(i=grt[1];i<=gr;i++)
	{
		a[1][i]=p[1];
	}
	for(i=2;i<=n;i++)
	{
		for(j=1;j<=gr;j++)
		{
			if((j-grt[i])<0)
			{
				a[i%2][j]=a[(i-1)%2][j];
			}
			else
			{
				a[i%2][j]=maxim(a[(i-1)%2][j-grt[i]]+p[i],a[(i-1)%2][j]);
			}
		}
	}
	printf("%d",a[n%2][gr]);
	return 0;
}