#include <iostream>
#include <conio.h>
#include <fstream>


#define inf 10000000;

using namespace std;

ifstream f("rucsac.in");
ofstream g("rucsac.out");

int n,gr;

struct item {int w,p; };

item a[5001];
long rez[10001];

int main()
{
    f >> n >> gr;
     for (int i=1; i<=n;++i)
       f >> a[i].w >> a[i].p;

    for (int i=1; i<=gr;++i)
        rez[i] = 0;


rez[0] = 0;
  for (int i=1;i<=n;i++)
  {
      for (int j=gr; j>0;--j)
      {
        if (j-a[i].w >=0 && rez[j-a[i].w] != 0 )
             if ( rez[j-a[i].w] + a[i].p > rez[j]  ) rez[j] = rez[j-a[i].w] + a[i].p;
         if (j-a[i].w == 0)
              if ( rez[j-a[i].w] + a[i].p > rez[j]  ) rez[j] = rez[j-a[i].w] + a[i].p;
      }

  }
     while (rez[gr] == 0)
     {
         gr--;
     }

     g << rez[gr];

    return 0;
}