#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;

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

int N, G;
int g[5005], v[5005];
int mdin[5005][10005];

int main(){

    fin >> N >> G;

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

    for(int greu = 1; greu <= G; greu++){
        for(int e = 1; e <= N; e++){
            if(g[e] > greu){
                mdin[e][greu] = mdin[e-1][greu];
            }else{
                mdin[e][greu] = max(mdin[e-1][greu], mdin[e-1][greu-g[e]] + v[e]);
            }
        }
    }

    fout << mdin[N][G];

    return 0;
}