#include <fstream>
#include <vector>
#define maxn 5010
#define maxg 10010
using namespace std;


ifstream f("rucsac.in");
ofstream g("rucsac.out");
vector<int> p(maxn),w(maxn);
int n,G;
int D[2][maxg];
int main()
{
 int i, j,l=0;
    f>>n>>G;
    for(i=1;i<=n;i++)
        f>>w[i]>>p[i];
        for(i=1;i<=n;++i,l=1-l)
            for(j=0;j<=G;j++)
        {
            D[1-l][j]=D[l][j];
             if(w[i]<=j)
                D[1-l][j]=max(D[1-l][j],D[l][j-w[i]]+p[i]);
        }
        g<<D[l][G];

}