#include <iostream>
#include <fstream>
#define nmax 5005
#define gmax 10005
using namespace std;
ifstream in("rucsac.in");
ofstream out("rucsac.out");
int g[nmax], c[nmax], a1[gmax], a2[gmax], N, G;

void read(){
    in>>N>>G;
    for(int i=1; i<=N; i++)in>>g[i]>>c[i];
}

void swpVec(){
    for(int i=1; i<=G; i++)a1[i]=a2[i];
}

void dp(){
    int i, j;
    for(i=1; i<=N; i++){
        swpVec();
        for(j=1; j<=G; j++){
            if(g[i]>j)a2[j]=a1[j];
            else a2[j]=max(a1[j], a1[j-g[i]]+c[i]);
        }
    }
}

int main(){
    read();
    dp();
    out<<a2[G];
    return 0;
}