#include <iostream>
#include <fstream>

struct Obiect{
    int w;
    int v;
};

#define MAXN 5010
#define MAXG 10010

int DP[MAXN][MAXG];

void copy_array(int to[], int from[], int N){

    for(int i = 1; i <= N; ++i){
        to[i] = from[i];
    }
}


int main(){

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

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

    Obiect obiecte[N + 1];
    for(int i = 1; i <= N; ++i){
        in >> obiecte[i].w >> obiecte[i].v;
    }

    int prev[G + 1] = {};
    for(int i = 1; i <= N; ++i){
        int curr[G + 1] = {};
        for(int j = 1; j <= G; ++j){
            curr[j] = prev[j];
            if(obiecte[i].w <= j){
                curr[j] = std::max(curr[j], prev[j - obiecte[i].w] + obiecte[i].v);
            }
        }
        copy_array(prev, curr, G);
    }

    out << prev[G];
    return 0;
}