#include <stdio.h>
#define max(p,q)((p>q)?(p):(q))

int dp[10010];
int main(){
	int n,m;
	scanf("%d%d",&n,&m);
	while(n--){
		int v,w;
		scanf("%d%d",&v,&w);
		for(int i=m-w;i>=0;i--)dp[i+w]=max(dp[i+w],dp[i]+v);
	}
	printf("%d\n",dp[m]);
}
