#include<bits/stdc++.h>
#define N 5001
#define G 10001
using namespace std;

int n,gm,g[N+1],c[N+1],viz[G+1][N+1],C[G+1],CMax[2][G],ans;

void read();
void solve();
void print();

int main()
{
    read();
    solve();
    print();

}

void read()
{
    freopen("rucsac.in","r",stdin);
    scanf("%d%d",&n,&gm);
    for(int i=1;i<=n;i++)
        scanf("%d%d",&g[i],&c[i]);
}

void solve()
{
   int S, k, i;

/*for (S=1; S<=gm; S++) CMax[S]=-1;

   for (S=0; S<=gm; S++)
    for (i=1; i<=n; i++)
       if (g[i]<=S  && CMax[S-g[i]]!=-1 && !viz[S-g[i]][i])
          if (CMax[S]<c[i]+CMax[S-g[i]])
  {CMax[S]=c[i]+CMax[S-g[i]];
  ans=max(ans,CMax[S]);
    for (k=1; k<=n; k++)
    viz[S][k]=viz[S-g[i]][k];
  viz[S][i]=1;
   }*/


   int d=0;
   for(i=1;i<=n;i++)
   {   d=1-d;
       for(S=0;S<=gm;S++)
       {
           CMax[1-d][S]=CMax[d][S];
           if(g[i]<=S)
            CMax[1-d][S]=max(CMax[1-d][S],CMax[d][S-g[i]]+c[i]);
       }
   }
   ans=CMax[d][gm];

}

void print()
{
    freopen("rucsac.out","w",stdout);
    printf("%d\n",ans);
    //for(int i=1;i<=n;i++)
   //     if(viz[gm][i]==1) printf("%d ",i);
}