#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream f("rucsac.in");
ofstream g("rucsac.out");
short int W[5001],P[5001];
int Matrix[3][5001];
int main()
{
    short int n,G;
    f>>n>>G;

      for(short int i=1;i<=n;i++)f>>W[i]>>P[i];

      for(short int i=1;i<=n;i++)
      {
          for(short int weight=1;weight<=G;weight++)
            if(W[i]<=weight)
                Matrix[2][weight]=max(Matrix[1][weight],(P[i]+Matrix[1][weight-W[i]]));

          for(short int weight=1;weight<=G;weight++)
              Matrix[1][weight]=Matrix[2][weight];
      }
    g<<Matrix[2][G];
}