#include <fstream>
using namespace std;
int n,G,v[5001],V[10001],g[5001],Vmax,i,gr;
ifstream f("rucsac.in");
ofstream h("rucsac.out");
int main()
{
    f>>n>>G;
    for(i=1;i<=n;i++)f>>g[i]>>v[i];
    for(i=1;i<=n;i++)
    for(gr=G-g[i];gr>=0;gr--)
    {
        if(V[g[i]+gr]<V[gr]+v[i])
        {
            V[g[i]+gr]=V[gr]+v[i];
            if(Vmax<V[g[i]+gr])Vmax=V[g[i]+gr];
        }
    }
    h<<Vmax<<"\n";
    return 0;
}