#include <bits/stdc++.h>

using namespace std;
int n,k,rez=0;
struct sigma
{
    int cost,greutate;
};
sigma v[5005];
int maxp[5005][1005];
 int Rezolv(int a,int c)
{
    if(a==n+1)
        return 0;
    if(maxp[a][c]==-1)
    {
        maxp[a][c]=Rezolv(a+1,c);
        if(c+v[a].greutate<=k)
            maxp[a][c]=max(maxp[a][c],Rezolv(a+1,c+v[a].greutate)+v[a].cost);
    }
    return maxp[a][c];

}
int main()
{
    ifstream cin("rucsac.in");
    ofstream cout("rucsac.out");
  cin>>n>>k;
  for(int i=0;i<=5000;i++)
    for(int j=0;j<=1000;j++)
    maxp[i][j]=-1;
  for(int i=1;i<=n;i++)
    cin>>v[i].greutate>>v[i].cost;
  cout<<Rezolv(1,0);
    return 0;
}