#include<fstream>
using namespace std;
ifstream in("rucsac.in");
ofstream out("rucsac.out");
int n,m,p[5005],g[5005],mat[2][5005],i,j,maxim;
int main(){
    in >> n >> m;
    for( i = 1; i <= n; i ++ ){
        in >> g[i] >> p[i];
    }
    for( i = 1; i <= n; i ++ ){
        for( j = 1; j <= m; j ++ ){
            if( j - g[i] >= 0 ){
                if( mat[(i-1)%2][j - g[i] ] + p[i] > mat[(i-1)%2][j] ){
                    mat[i%2][j] = mat[(i-1)%2][j - g[i] ] + p[i];
                }
                else{
                    mat[i%2][j] = mat[(i-1)%2][j];
                }
            }
            else{
                mat[i%2][j] = mat[(i-1)%2][j];
            }
            if( mat[i%2][j] > maxim ){
                maxim = mat[i%2][j];
            }
        }
    }
    out << maxim ;

    return 0;
}