#include <fstream>

using namespace std;

struct obiect
{
    int W, P;
}a[5000];

int mem[5000][5000];

void init(int n, int g)
{
    for(int i=0; i<=n+1; i++)
        for(int j=0; j<=g+1; j++)
            mem[i][j] = -1;
}

void citire(int &n, int &g)
{
    ifstream fin("rucsac.in");

    fin >> n >> g;

    for(int i=1; i<=n; i++)
        fin >> a[i].W >> a[i].P;
}

int dinamica(int n, int c)
{
    int result;
    if(mem[n][c] == -1)
    {
        if(n==0 || c==0)
            result = 0;
        else if(a[n].W>c)
            result = dinamica(n-1, c);
        else
        {
            int t1 = dinamica(n-1, c);
            int t2 = a[n].P+dinamica(n-1, c-a[n].W);
            result = (t1 > t2)?t1:t2;
        }
        mem[n][c] = result;
    }
    return result;
}

int main()
{
    ofstream fout("rucsac.out");

    int n, g;

    citire(n, g);
    init(n, g);

    fout << dinamica(n, g);

    return 0;
}