#include <bits/stdc++.h>

using namespace std;
ifstream f("rucsac.in");
ofstream g("rucsac.out");
int n, G;
int dp[100005];
int w[5005],p[5005];

int main()
{
  f>>n>>G;
  for(int i = 1;i <= n;++i)
    f>>w[i]>>p[i];
  int maxim = 0;
  for(int i = 1;i <= n;++i)
    for(int j = G - w[i];j >= 0;--j)
      if(dp[j + w[i]] < dp[j] + p[i])
      {
        dp[j + w[i]] = dp[j] + p[i];
        maxim = max(maxim, dp[j + w[i]]);
      }
  g<<maxim;
  return 0;
}