#include <fstream>
using namespace std;
ifstream in("rucsac.in");
ofstream out("rucsac.out");
int W,n;
int weight[5005], value[5005], D[10005];
int main()
{
     in >> n >> W;
     for(int i=1; i<=n; i++)
          in >> weight[i] >> value[i];

     for(int i =1; i<=n; i++)
          for(int w=W; w>0; w--)
          if( weight[i] <= w)
          D[w] = max( D[w], D[w - weight[i]] + value[i]);

     out << D[W];

    return 0;
}