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

using namespace std;

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

int n,S,w[nmax],p[nmax],prevv[gmax],curr[gmax];

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++) prevv[i]=0;

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

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

    out << curr[S];
}

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