#include<stdio.h>
#include<string.h>

int a[5001],p[5001],s1[10001],s2[10001];

int max(int a,int b)
{
if(a>b)
	return a;
return b;
}

int main()
{
freopen("rucsac.in","r",stdin);
freopen("rucsac.out","w",stdout);
int n,i,g,j;
scanf("%d%d",&n,&g);
for(i=1;i<=n;i++)
	scanf("%d%d",&a[i],&p[i]);
for(i=1;i<=n;i++)
	{
	for(j=1;j<a[i];j++)
		s2[j]=s1[j];
	for(j=a[i];j<=g;j++)
		s2[j]=max(s1[j],s1[j-a[i]]+p[i]);
	memcpy(s1,s2,sizeof(s2));
	}
printf("%d",s1[g]);
return 0;
}