#include <fstream>
#include <algorithm>
using namespace std;
int D[10001][10001],G[5001],P[5001],n,C;
ifstream f("rucsac.in");
ofstream g("rucsac.out");

int main()
{
    f>>n>>C;
    for(int i=1; i<=n; i++)
       {f>>G[i]>>P[i];
         if(G[i]<=C)
         if(D[1][G[i]]<P[i])
            D[1][G[i]]=P[i];
       }

for(int i=2; i<=n; i++)
        for(int j=1; j<=C; j++)
            if(j>G[i])
            D[i][j]=max(D[i-1][j],D[i-1][j-G[i]]+P[i]);
             else
                D[i][j]=D[i-1][j];

   g<<D[n][C];


    return 0;
}