#include <iostream>
#include <fstream>


const int NMAX = 5002;
const int GMAX = 10002;

struct Obiect{

    int V;
    int W;

};


Obiect Obiecte[NMAX];
long long int prev[GMAX];

int main(){

    std::ifstream in("rucsac.in");
    std::ofstream out("rucsac.out");

    int N, G;
    in >> N >> G;

    for(int i = 1; i <= N; ++i){
        in >> Obiecte[i].W >> Obiecte[i].V;
    }


    for(int i = 1; i <= N; ++i){
        long long int curr[G + 1];
        for(int j = 1; j <= G; ++j){
            if(Obiecte[i].W <= j){
                curr[j] = std::max(prev[j], prev[j - Obiecte[i].W] + Obiecte[i].V);
            }
            else{
                curr[j] = prev[j];
            }
        }

        for(int j = 1; j <= G; ++j){
            prev[j] = curr[j];
        }
    }

    out << prev[G];


    return 0;
}