# 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],a[V],b[V],n,g,i,j,sol;
int main () {
    fin>>n>>g;
    for(i=1;i<=g;i++)
        f[i]=INF;
    for(i=1;i<=n;i++)
        fin>>a[i]>>b[i];
    for(i=1;i<=n;i++){
        for(j=g;j>=0;j--){
            if(f[j]!=INF&&j+a[i]<=g){
                f[j+a[i]]=max(f[j+a[i]],f[j]+b[i]);
                if(f[j+a[i]]>sol)
                    sol=f[j+a[i]];
            }
        }
    }
    fout<<sol<<"\n";
    return 0;
}