#include<stdio.h>

#define MAX 101

int max(int a,int b,int c)
{
	int M;
	M=a;
	if(M < b) M=b;
	if(M < c) M=c;
	return M;
}

int main(void)
{
	int i,j,N,W,v[MAX],w[MAX],dp[MAX][10001];
	
	scanf("%d%d",&N,&W);
	v[0]=0;
	w[0]=0;
	for(i=1;i<=N;i++)
	{
		scanf("%d%d",&v[i],&w[i]);
	}
	for(i=0;i<=W;i++)
	{
		dp[0][i]=0;
	}
	for(i=1;i<=N;i++)
	{
		for(j=0;j<=W;j++)
		{
			if(w[i]<=j)
			{
				dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i],dp[i][j-w[i]]+v[i]);
			}
			else
			{
				dp[i][j]=dp[i-1][j];
			}
		}
	}
	printf("%d\n",dp[N][W]);
	return 0;
}