#include <iostream>
#include <fstream>

using namespace std;

ifstream in("rucsac.in");
ofstream out("rucsac.out");
int n,G,g[5001],p[5001],opt[10001],maxx;

void olvas(){
    int i;
    in>>n>>G;
    for(i = 1; i <= n; ++i) in>>g[i]>>p[i];
}

void megold(){
    int i,j;
    opt[0] = 0;
    maxx = 0;
    for(i = 1; i <= n; i++){//minden tárgy esetén
        for(j = G - g[i]; j >= 0; --j){
            if(j != 0){
                if(opt[j] != 0) //ha létezik j súly
                    if(opt[j + g[i]] < opt[j] + p[i])//ha hozzáadom az i tárgyat és jobb az eredmény
                        opt[j + g[i]] = opt[j] + p[i];
            }
            else {
                if(opt[g[i]] < p[i]) opt[g[i]] = p[i]; //ha csak az i tárgy vezet megfelelő eredményre
            }
            if(maxx < opt[j+g[i]]) maxx = opt[j + g[i]];
        }
    }
    out<<maxx;
}

int main()
{
    olvas();
    megold();
    return 0;
}