# include <fstream>
# define DIM 10010
# define V 5010
# define INF 11000000
using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
int f[DIM],pmax,maxim,c[V],g[V],G,n,i,j,sol;
int main () {
    fin>>n>>G;
    for(i=1;i<=n;i++){
        fin>>g[i]>>c[i];
    }
    for(i=1;i<=G;i++){
        f[i]=-INF;
    }
    for(i=1;i<=n;i++){
        for(j=G;j>=0;j--){
            if(f[j]!=-INF){
                if(j+g[i]<=G){
                    f[j+g[i]]=max(f[j+g[i]],f[j]+c[i]);
                    sol=max(sol,f[j+g[i]]);
                }
            }
        }
    }
    fout<<sol<<"\n";
    return 0;
}