#include <fstream>
#define IN_FILE "rucsac.in"
#define OUT_FILE "rucsac.out"
#define MAXN 5010
#define MAXG 10010
#include <algorithm>
#include <vector>

using namespace std;
ifstream fin(IN_FILE);
ofstream fout(OUT_FILE);
int n,g,w,p,optim[MAXG];
struct bag {
    int w,p;
} v[MAXN];
int main() {
    fin>>n>>g;
    for (int i=1;  i<=n;  ++i) {
        fin>>v[i].w>>v[i].p;

    }
    optim[0]=0;
    int sol=0;

    for (int i=1;  i<=n;  ++i)
        for (int j=g-v[i].w; j >= 0;  --j)
            if ( optim[j + v[i].w] < optim[j] + v[i].p ) {
                optim[ j + v[i].w ]=optim[j] + v[i].p;
                if( optim[j+v[i].w] > sol)
                    sol = optim[j+v[i].w];
            }


    fout<<sol;


    return 0;
}