#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
int n,g,i,gc,s1,s2,g1,g2,D[10010];
struct cell
{
    int w,p;
}v[5010];
int main()
{
    fin>>n>>g;
    for(i=1;i<=n;i++)
        fin>>v[i].w>>v[i].p;
    for(i=1;i<=n;i++)
        for(gc=g-v[i].w;gc>=0;gc--)
            D[gc+v[i].w]=max(D[gc+v[i].w],D[gc]+v[i].p);
    fout<<D[g];
    fin.close();
    fout.close();
    return 0;
}