#include <iostream>
#include <fstream>


#define nmax 5001
#define gmax 10001

int D[nmax][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(register int gC = 0; gC <= G; gC++){
            if (g[i] <= gC){
                D[i][gC] = max(D[i - 1][gC], D[i-1][gC - g[i]] + v[i]);
            }
        }
    }

    out << D[N][G];

    in.close();
    out.close();
    return 0;
}