#include <fstream>

using namespace std;


ifstream cin("rucsac.in");
ofstream cout("rucsac.out");

int dp[2][100001];

inline void wZERO(const int& w)
{
  for(int i=0; i<w; i++)
  {
    cout<<"0 ";
  }
  cout<<"\n";
}

int main()
{
  ios::sync_with_stdio(false);

  int n, w, xv, xw; bool t=1;
  cin>>n>>w;

  //wZERO(w);

  for(int i=0; i<n; i++)
  {
    cin>>xw>>xv;
    
    for(int j=0; j<=w; j++)
    {
      if(j<xw)
        dp[t][j]=dp[!t][j];
      else
      {
        dp[t][j]=max(dp[!t][j], xv+dp[!t][j-xw]);
      }
      //cout<<dp[t][j]<<" ";
    }
    t=!t;
    //cout<<"\n";
  }

  cout<<dp[!t][w];

  return 0;
}