///patratele
#include <bits/stdc++.h>
using namespace std;

#define MOD 666013

ifstream fin("rucsac.in");
ofstream fout("rucsac.out");

long long i,dp[10010],n,w[5010],p[5010],g,j,ras=-1;

int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  fin>>n>>g;
  for(i=1;i<=n;i++)
      fin>>w[i]>>p[i];
  for(i=1;i<=n;i++)
    for(j=g;j>=w[i];j--)
      {
        dp[j]=max(dp[j-w[i]]+p[i],dp[j]);
        ras=max(ras,dp[j]);
      }
  fout<<ras;
  return 0;
}