#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

typedef long long ll;
const int NMAX = 2e4+5;
const int EMAX = 2e5+5;
const int KMAX = 2e6+5;

int t[NMAX];
int c[NMAX];
int p[NMAX];

int dp[2][KMAX];

int main(){

	freopen("rucsac.in","r",stdin);
	freopen("rucsac.out","w",stdout);

	int n, k;
	scanf("%d%d", &n, &k);

	for(int i=0; i<n; ++i){
		scanf("%d%d", &c[i], &p[i]);
	}

	for(int i=0; i<n; ++i){
		for(int j=0; j<=k; ++j){
			if(j - c[i] < 0) 
				dp[i%2][j] = dp[(i+1)%2][j];
			else 
				dp[i%2][j] = max(dp[(i+1)%2][j], dp[(i+1)%2][j-c[i]] + p[i]);
		}
	}

	printf("%d\n", dp[(n+1)%2][k]);

	return 0;
}