#include <fstream>

using namespace std;

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

int N, G;
int w[5005], p[5005];
int m[10005][2];

bool s = 1;

int main(){

    fin >> N >> G;

    for(int i = 1; i <= N; i++){
        fin >> w[i] >> p[i];
    }

    for(int i = 1; i <= N; i++){
        for(int wi = 1; wi <= G; wi++){
            if(w[i] > wi){
                m[wi][s] = m[wi][1-s];
            }else{
                m[wi][s] = max(m[wi][1-s], m[wi-w[i]][1-s] + p[i]);
            }
        }
        s = 1-s;
    }

    fout << m[G][1-s];

    return 0;
}