#include <fstream>
#include <cstdio>
#include <algorithm>

using namespace std;

ifstream fin("rucsac.in");
ofstream fout("rucsac.out");

#define MAXN 1010
#define MAXG 10010

int N,G,Pmax;
int W[MAXN],P[MAXN];
int D[MAXN][MAXG];

int main()
{
    int i,cw;

    fin>>N>>G;
    for(i=1;i<=N;i++)
        fin>>W[i]>>P[i];

    // Dinamica D[i][cw] - profitul maxim pe care-l putem obtine adaugand o submultime a primelor i obiecte, insumand greutatea cw

    for(i=1;i<=N;++i)
        for(cw=0;cw<=G;++cw)
        {
            // Mai intai nu punem obiectul i.  -- cum ar fi fara obiectul i, valori la fel
            D[i][cw] = D[i-1][cw];
            // Daca acest lucru duce la o solutie curenta mai buna, adaugam obiectul i la o solutie anterioara. -- daca scoatem o greutate g[i] si adaugam p[i], ajungem la o solutie mai eficienta?
            if(W[i] <= cw)
                D[i][cw] = max(D[i][cw], D[i - 1][cw - W[i]] + P[i]);
        }
    /*for(i=0;i<=N;++i)
        {for(cw=0;cw<=G;++cw)
            fout<<D[i][cw]<<" ";
        fout<<'\n';
        }*/
    fout<<D[N][G];

    return 0;
}