#include <iostream>
#include <fstream>
std::ifstream fin ("rucsac.in");
std::ofstream fout("rucsac.out");

int n,g;
int v[5050],w[5050];
int d[2][10500];
int maxx;
int main()
{
  fin>>n>>g;
  for(int i=1;i<=n;i++)
    fin>>w[i]>>v[i];
  for(int i=1;i<=n;i++)
  {
    for(int j=1;j<=g;j++)
    {
      if(j>=w[i])
      {
        d[i%2][j]=std::max(d[(i+1)%2][j], d[(i+1)%2][j-w[i]]+v[i]);
        if(d[i%2][j]>maxx)
          maxx=d[i%2][j];
      }
      else
        d[i%2][j]=d[(i+1)%2][j];
    }
  }
  fout<<maxx;
}