#include<stdio.h>

int K[10005][10005];
void knapsack(int n, int wMax,int W[],int b[])
{

	for(int i=1;i<=n;i++)
	{
		for(int w=0;w<=wMax;w++)
		{
			if(W[i] <= w)
			{
				if(b[i] + K[i-1][w-W[i]] > K[i-1][w])
				{
					K[i][w] = b[i] + K[i-1][w-W[i]];
				}else
				{
					K[i][w] = K[i-1][w];
				}
			}else
			{
				K[i][w]=K[i-1][w];
			}
		}
	}
	
	printf("%d\n",K[n][wMax]);
}


int main()
{
	int N,Weight;
	int V[10000],W[10000];
	int answer;
	
	scanf("%d %d",&N,&Weight); getchar();
	for(int i=1;i<=N;i++)
	{
		scanf("%d %d",&V[i],&W[i]); getchar();
	}
	
	knapsack(N,Weight,W,V);
	
	return 0;
}
