#include <stdio.h>
int main(){
	int n,m;//n:個数、m:ナップサックの上限重量
	scanf("%d %d",&n,&m);
	int dp[n][m+1];
	int v[n],w[n];//v:価値,w:重量
	int i,j;
	for(i=0;i<n;i++){
		scanf("%d %d",&v[i],&w[i]);
	}
	for(i=0;i<n;i++){
		for(j=0;j<=m;j++){
			dp[i][j]=0;
		}
	}
	for(i=w[0];i<=m;i++){
		dp[0][i]=v[0];
	}
	int a;//比較用
	for(i=1;i<n;i++){
		for(j=0;j<=m;j++){
			a=0;
			if(j>=w[i]){
				a=dp[i-1][j-w[i]]+v[i];
			}
			dp[i][j]=dp[i-1][j]>a?dp[i-1][j]:a;
		}
	}
	printf("%d\n",dp[n-1][m]);
	return 0;
}