#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[2][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[1][weight]=max(Matrix[0][weight],(P[i]+Matrix[0][weight-W[i]]));

            else Matrix[1][weight]=Matrix[0][weight];

          for(short int weight=1;weight<=G;weight++)
              Matrix[0][weight]=Matrix[1][weight];
      }
    for(int i=G;i>=1;i--)
    if(Matrix[1][i]){g<<Matrix[1][i];break;}
}