#include <fstream>
using namespace std;
ifstream fi("rucsac.in");
ofstream fo("rucsac.out");
struct chef{
int g;
int v;
}Bornea[5000];
int n,i,j,k,g,a[1000][1000];
int main()
{
fi>>n>>g;
for(i=1;i<=n;i++){
fi>>Bornea[i].g>>Bornea[i].v;
}
for(i=1;i<=n;i++){
for(j=1;j<=g;j++){
if(j<Bornea[i].g)
a[i][j]=max(a[i][j-1],a[i-1][j]);
else{
a[i][j]=max(max(a[i][j-1],a[i-1][j]),
Bornea[i].v+a[i-1][j-Bornea[i].g]);
}
}
}
/*
for(i=1;i<=n;i++){
for(j=1;j<=g;j++)
fo<<a[i][j]<<' ';
fo<<'\n';
}
*/
fo<<a[n][g];
return 0;
}