#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
int N,G,d[10001],w[5001],p[5001],Max,cw;
int main()
{   fin>>N>>G;
    for(int i=1;i<=N;i++)
        fin>>w[i]>>p[i];
        Max=0;

    for(int i=1;i<=N;i++)
        {   cw=G;
        while(cw>=w[i])
        {   if(d[cw]<d[cw-w[i]]+p[i])
        {
            d[cw]=d[cw-w[i]]+p[i];
            if(d[cw]>Max)
                Max=d[cw];
        }
        --cw;}
        }
        fout<<Max;
    return 0;
}