#include <fstream>
#define MAX 5004
#define GMAX 10004
using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
int n,g,maxi;
struct obiect{
    int g,val;//greutate,valoare
}A[MAX];
int Dp[2][GMAX];
void afisare();
int main(){
    int i,j;
    fin>>n>>g;
    for(i=1;i<=n;++i)fin>>A[i].g>>A[i].val;
    for(i=1;i<=n;++i){
        if(A[i].g<=g)Dp[1][A[i].g]=A[i].val;
        for(j=1;j<=g;++j){
            if(Dp[0][j]){
                if(Dp[1][j]<Dp[0][j])Dp[1][j]=Dp[0][j];
                if(g>=j+A[i].g){
                    if(Dp[1][j+A[i].g]<Dp[0][j]+A[i].val) Dp[1][j+A[i].g]=Dp[0][j]+A[i].val;
                    if(Dp[1][j+A[i].g]>maxi)maxi=Dp[1][j+A[i].g];
                }
            }
            if(Dp[1][j]) Dp[0][j]=Dp[1][j];
        }
        //afisare();
    }
    fout<<maxi<<'\n';
    return 0;
}
void afisare(){
    int i,j;
    for(i=0;i<=1;++i){
        for(j=1;j<=g;++j){
            fout<<Dp[1][j];
            if(Dp[i][j]>=10)fout<<' ';
            else fout<<"  ";

        }fout<<'\n';
    }
    fout<<'\n';
}