#include <fstream>
#include <iostream>
using namespace std;

ifstream fin("rucsac.in");
ofstream fout("rucsac.out");

int N,G,Pmax;

int W[5005],P[5005],D[5][10005];

int main()
{
  int i,cw;
    fin>>N>>G;

    for(i=1;i<=N;i++)
        fin>>W[i]>>P[i];
    for(cw = 0; cw <= G;cw++)
        {
            D[2][cw] = D[1][cw];

            if(W[1] <= cw)
                D[2][cw] = max(D[2][cw], D[1][cw - W[1]] + P[1]);
        }
    for(i=0;i<=G;i++)   D[1][i]=D[2][i];

    for(i = 2; i <= N;i++)
    {
        for(cw = 0; cw <= G;cw++)
        {
            if(W[i] <= cw)
                D[2][cw] = max(D[2][cw], D[1][cw - W[i]] + P[i]);
        }
      for(int j=0;j<=G;j++)   D[1][j]=D[2][j];
    }
    Pmax=D[1][G];
    cout<<Pmax;
    return 0;
}