#include <fstream>

using namespace std;

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

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

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

    fout << m[N][G];

    return 0;
}