#include<stdio.h>
int greutati[10001],profituri[10001];
int dp[2][10001],N,G;
void citire()
{
	scanf("%d%d",&N,&G);
	for(int i=1;i<=N;i++)
		scanf("%d%d",&greutati[i],&profituri[i]);
}
inline int maxim(int x,int y)
{if(x>y) return x; return y;}
void dinamica()
{
	int x=1;
	for(int i=1;i<=N;i++)
	{
		x=1-x;
		for(int j=1;j<=G;j++)
		{
			if(greutati[i]<=j)
				dp[1-x][j]=maxim(dp[x][j],dp[x][j-greutati[i]]+profituri[i]);
			else
				dp[1-x][j]=dp[x][j];
		}
	}
	printf("%d",dp[0][G]);

}
int main()
{
	freopen("rucsac.in","r",stdin);
	freopen("rucsac.out","w",stdout);
	citire();
	dinamica();
	return 0;
}