#include <fstream>

using namespace std;

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

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

int main(){

    fin >> N >> G;

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

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

    fout << m[G][N];

    return 0;
}