#include <stdio.h>

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


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