#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 schimb;

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][1] = m[wi][0];
            }else{
                m[wi][1] = max(m[wi][0], m[wi-w[i]][0] + p[i]);
            }
        }

        for(int wi = 1; wi <= G; wi++){
            m[wi][0] = m[wi][1];
        }
    }

    fout << m[G][1];

    return 0;
}