#include <iostream>
#include <fstream>
#define nmax 5005
#define nmax1 10005

using namespace std;

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

int n,S,w[nmax],p[nmax],prev[nmax1],curr[nmax1];

void citire(){
	in >> n >> S;
	for (int i=1; i<=n; i++)
		in >> w[i] >> p[i];
}

void work_hard(){
	for (int i=1; i<=n; i++) prev[i]=0;

	for (int i=1; i<=n; i++){
		for (int j=1; j<=S; j++){
				if (w[i]<=j) {
					curr[j]=prev[j-w[i]]+p[i];
					curr[j]=max(prev[j], p[i]+prev[j-w[i]]);
				}
                else {
				curr[j]=prev[j];
                }
		}

        if (i<n) for(int j=1; j<=S; j++) prev[j]=curr[j];
    }

    out << curr[S];
}

int main() {
	citire();
	work_hard();
	return 0;
}