#include <iostream>
#include <fstream>


#define nmax 5001
#define gmax 10001

int D[gmax];
int v[nmax], g[nmax];
int N, G;

int max(int a, int b){
    return (a > b)?a:b;
}

int main (){

    std::fstream in, out;
    in.open("rucsac.in", std::ios::in);
    out.open("rucsac.out", std::ios::out);


    in >> N >> G;

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

    for (int i = 1; i <= N; i++){
        for (int cw = G; cw >= g[i]; cw--){
            D[cw] = max(D[cw], D[cw - g[i]] + v[i]);
        }
    }


    out << D[G];

    in.close();
    out.close();

    return 0;
}