#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#define max(a, b)	(((a) > (b)) ? (a) : (b))		/* ２個の値の最大値 */
#define min(a, b)	(((a) < (b)) ? (a) : (b))		/* ２個の値の最小値 */
#define ENTER		printf("\n")					/* 改行プリント */
/********************************************************************************************************************************/
/* main *************************************************************************************************************************/
/********************************************************************************************************************************/
int DEBUG = 1;										/* デバッグプリント 提出時は0 */

int dp[10001] = {0};

int main()
{
	int		N,W,v[101],w[101],i,j;
	//int		*dp;
	scanf("%d %d", &N, &W);
	for(i=1; i<=N; i++) {
		scanf("%d %d",&v[i],&w[i]);
	}
/*
	for(i=1;i<=N;i++) {
		for(j=0;j+w[i]<=W;j++) {
				dp[j+w[i]] = max( dp[j+w[i]] , dp[j]+v[i]);
		}
	}
*/
	for(i=1;i<=N;i++) {
		for(j=w[i];j<=W;j++) {
				dp[j] = max( dp[j] , dp[j-w[i]]+v[i]);
		}
	}

	printf("%d\n",dp[W]);

	return 0;
}

