#include <bits/stdc++.h>
#define ll long long
using namespace std;

int ks[5005][10005];
pair<int, int> v[5005];
int n,g;

ifstream fin("rucsac.in");
ofstream fout("rucsac.out");

int knapsack() {
	int i, j, mprof=0;
	for(i = 1; i <= n; i++) {
		for(j = 1; j <= g; j++) {
			if(v[i].first > j) ks[i][j] = ks[i-1][j];
			else ks[i][j] = max(ks[i-1][j], ks[i-1][j-v[i].first] + v[i].second);
			if(ks[i][j] > mprof) mprof = ks[i][j];
		}
	}
	return mprof;
}

int main(){
	fin>>n>>g;
	int w,p;
	for(int i = 1; i <= n; i++) {
		cin>>w>>p;
		v[i].first = w;
	   	v[i].second = p;
	}
	fout<<knapsack();
}