#include<bits/stdc++.h>
using namespace std;
#define int long long
int dp[123][123456];
int N,W,price[123],wt[123];
int32_t main()
{
   cin >> N>>W;
   for(int i=0;i<N;i++)
   {
       cin>> wt[i] >> price[i];
   }

   for(int i=1;i<=N;i++)
   {
      for(int j=1;j<=W;j++)
      {
          if(wt[i-1]<=j)
          {
            dp[i][j] = max(dp[i-1][j],dp[i-1][j-wt[i-1]]+price[i-1]);
          }
          else
          dp[i][j] = dp[i-1][j];
      }
   }

   cout<<dp[N][W]<<"\n";

}

///space optimization

#include<bits/stdc++.h>
using namespace std;
#define int long long
int dp[123456];
int N,W,price[123],wt[123];
int32_t main()
{
   cin >> N>>W;
   for(int i=0;i<N;i++)
   {
       cin>> wt[i] >> price[i];
   }

   for(int i=0;i<N;i++)
   {
      for(int j=W-wt[i];j>=0;j--)
      {
         dp[j+wt[i]] = max(dp[j+wt[i]],dp[j]+price[i]);
      }
   }

   cout<<dp[W]<<"\n";

}