#include <fstream>

using namespace std;
ifstream f("rucsac.in");
ofstream gout("rucsac.out");

int n,g,w[10001],p[10001],i,j,t[10001][10001],k;
int main()
{f>>n>>g;
for(i=1;i<=n;i++){f>>w[i]>>p[i];}

for(i=0;i<=g;i++)
    t[0][i]=0;
for(k=1;k<=n;k++){
    i=k%2;
if(i==1){

    for(j=0;j<=g;j++)
{
    if(w[k]>j)
        t[i][j]=t[i-1][j];
    else t[i][j]=max(t[i-1][j], t[i-1][j-w[k]]+p[k]);
}
}

else{
        for(j=0;j<=g;j++)
{
    if(w[k]>j)
        t[i][j]=t[i+1][j];
    else t[i][j]=max(t[i+1][j], t[i+1][j-w[k]]+p[k]);
}
}


}
gout<<t[i][g];
    return 0;
}