#include <iostream>
#include <algorithm>
using namespace std;

int m[2][10002],n,g,p[5001],w[5001];

int main(){
	freopen("rucsac.in","r",stdin);
	freopen("rucsac.out","w",stdout);
	scanf("%d%d",&n,&g);
	for(int i = 0; i < n; i++)
		scanf("%d%d",&w[i],&p[i]);
	
	for(int i = 1; i <= n; i++){
		 for(int c = 0; c <= g; c++){
			if(w[i - 1] > c)
				m[(i & 1)][c] = m[((i - 1) & 1)][c];
			else
				m[(i & 1)][c] = max(m[((i - 1) & 1)][c],m[((i - 1) & 1)][c - w[i - 1]] + p[i - 1]);
		 }
	}
	printf("%d\n",m[(n & 1)][g]);

	return 0;
}