#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stdio.h>

using namespace std;


long long int w[5003],v[5003],dp[10003];	

int main(){
	freopen("rucsac.in","r",stdin);
	freopen("rucsac.out","w",stdout);
	int n, g;
	scanf("%d%d",&n,&g);
	for(int i=1;i<=n;i++)scanf("%d%d",&w[i],&v[i]);
	
	for(int i=1;i<=n;i++)
	for(int j=g;j>=w[i];j--)dp[j]=max(dp[j],dp[j-w[i]]+v[i]);	
	
	printf("%d",dp[g]);
}