#include<fstream>
using namespace std;
#define MAX 10010
int result[2][MAX];

int main(){
ifstream in("rucsac.in"); ofstream out("rucsac.out");
int N,G,l=0,i,j;
in>>N>>G;
int g[N+1],p[N+1];
for(i=1;i<=N;i++) in>>g[i]>>p[i];

for(i=1;i<=N;++i, l=1-l)
  for(j=0;j<=G;++j){
     result[1-l][j]=result[l][j];
     if(j-g[i]>=0 && result[l][j-g[i]]+p[i]>result[1-l][j]) result[1-l][j]=result[l][j-g[i]]+p[i];
  }

out<<result[l][G];     

return 0;
}