#include <bits/stdc++.h>
#define NMAX 5001
#define NMAXG 10010
using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
int w[NMAX],p[NMAX];
int N,G;
int D[NMAXG];
int main()
{
    int i,cw;
    fin>>N>>G;
    for(i=1;i<=N;++i)
    {
        fin>>w[i]>>p[i];
    }
    int l=0;
    for(i=1;i<=N;++i)
    {
        for(cw=G;cw>=1;--cw)
        {
            if(w[i]<=cw)
            D[cw]=max(D[cw],D[cw-w[i]]+p[i]);
        }
    }
    int Pmax=D[G];
    fout<<Pmax;
    return 0;
}