#include <iostream>
#include <fstream>
using namespace std;

#define nmax 5001
#define gmax 10001
ifstream in("rucsac.in");
ofstream out("rucsac.out");

int n,G,i,j;
int W[nmax],V[nmax],cur[gmax],pre[gmax];

void dp(){
    
    for (i=1; i<=G; i++){
        for (j=1; j<=G; j++)
            if (W[i]<=j)
                cur[j]=max(pre[j], V[i]+pre[j-W[i]]);
            else cur[j]=pre[j];
        
        for (j=1; j<=G; j++) pre[j]=cur[j];
    }
    
    out << cur[G] << "\n";
    
}

int main(){
    
    in >> n >> G;
    
    for (i=1; i<=n; i++)
        in >> W[i] >> V[i];
    
    dp();
    
    return 0;
}