#include <fstream>
#include <algorithm>
#define DMAX 5001
#define IN "rucsac.in"
#define OUT "rucsac.out"

using namespace std;
ifstream fin (IN);
ofstream fout (OUT);

int n, G;
int w[DMAX], p[DMAX];
int dp[2][2*DMAX];
bool uz[DMAX];

void read();
void pd();

int main()
{
    read();
    pd();
    return 0;
}
void read()
{
    fin>>n>>G;
    for (int i=1; i<=n; ++i)
        fin>>w[i]>>p[i];
}
void pd()
{
    int i, cw, l=0;
    for (i=1; i<=n; ++i, l=1-l)
    {
        for (cw=0; cw<=G; ++cw)
        {
            dp[1-l][cw]=dp[l][cw];
            if (w[i]<=cw)
                dp[1-l][cw]=max(dp[1-l][cw],dp[l][cw-w[i]]+p[i]);
        }
    }
    fout<<dp[l][G];
}
/*#include <fstream>
#define GMAX 10010
#define NMAX 5004

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

void citire();
void pd();
void afisare();

int G,n,lc=2,lp=1;
int g[NMAX],p[NMAX];
int pmax[3][2*NMAX];
int maxim;


int main()
{
    citire();
    pd();
    afisare();
    return 0;
}
void pd()
{
    int i,j;
    for (i=1;i<=G;i++)
         if (g[1]<=i) pmax[1][i]=p[1];
    for (i=2;i<=n;i++)
         {for (j=1;j<=G;j++)
              {
               maxim=pmax[lp][j];
               if (g[i]<=j && maxim<p[i]+pmax[lp][j-g[i]])
                   maxim=p[i]+pmax[lp][j-g[i]];
               pmax[lc][j]=maxim;
              }
          lc=3-lc; lp=3-lp;
         }
}
void afisare()
{
    fout<<maxim<<'\n';
}
void citire()
{
    int i;
    fin>>n>>G;
    for (i=1;i<=n;i++)
         fin>>g[i]>>p[i];
}
*/