#include <fstream>

using namespace std;
#define MXN 5001
#define MXG 5001
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
int D[MXN][MXG];
int n,g;
int w[MXN],p[MXG];
int max(int a, int b)
{
    if(a>b)
        return a;
    else return b;
}
int rucsac(int i,int j)
{
    if(i==0)
        return 0;
    if(D[i][j]!=0)
        return D[i][j];
        if(j<w[i]) return D[i-1][j]=rucsac(i-1,j);
        return D[i][j]=max(rucsac(i-1,j),rucsac(i-1,j-w[i])+ p[i]);



}
int main()
{
    int i;
    fin>>n>>g;
    for(i=1;i<=n;i++)
        fin>>w[i]>>p[i];
    fout<<rucsac(n,g);
    fin.close();
    fout.close();
    return 0;
}