#include <fstream>
#define GMAX 10001
#define NMAX 5001
using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
int n,g,w[NMAX],p[NMAX],pmax[GMAX];
void citire();
int main()
{
    int i,x;
    citire();
    for (i=1; i<=n; i++)
        for (x=g-w[i]; x>=0; x--)
        {
            if (pmax[x+w[i]]<p[i]+pmax[x]) pmax[x+w[i]]=p[i]+pmax[x];
        }
        fout<<pmax[g]<<'\n';
    return 0;
}
void citire()
{
    int i;
    fin>>n>>g;
    for (i=1; i<=n; i++) fin>>w[i]>>p[i];
}