#include <iostream>
#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[MXN];
int maxx(int i, int j)
{
    if(i>j)
    {
        return i;
    }
    return j;
}
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]=maxx(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;
}