#include <iostream>
#include <fstream>
using namespace std;
ifstream f("rucsac.in");
ofstream g1("rucsac.out");
int n,g,gr[5005],v[5005],best[10005][3];
void Read()
{ int i;
  f>>n>>g;
 for(i=1;i<=n;i++) f>>gr[i]>>v[i];
}
void Solve()
{ int i,j,sol=0;

 for(i=1;i<=n;i++)
 { best[gr[i]][2]=v[i];
 for(j=1;j<=g;j++)
 { if (best[j][1] && j+gr[i]<=g) { best[j+gr[i]][2]=best[j][1]+v[i];}
   best[j][1]=max(best[j][1],best[j][2]);  }
 }
 sol=g;
 while(!best[sol][1]) sol--;
 g1<<best[sol][1];
}
int main()
{ Read();
  Solve();
    return 0;
}