#include <fstream>
#include<vector>
using namespace std;
vector<int> g(5002),p(5002);
ifstream cin("rucsac.in");
ofstream cout("rucsac.out");
int n,G,gr,pr;
int main()
{
 cin>>n>>G;
 if(n==0 || G==0) cout<<0;
 else{
 for(int i=1;i<=n;i++)
 {
     cin>>gr>>pr;
     for(int j=gr;j<=G;j++) g[j]=max(p[j],p[j-gr]+pr);
     p=g;
 }
 cout<<g[G];
 }
 return 0;
}