#include <fstream>

using namespace std;

ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
int n,G,v[5005],g[5005],d[2][5005],l;
int main()
{
   fin>>n>>G;
   for(int i=1;i<=n;i++)
    fin>>g[i]>>v[i];
    l=1;
   for(int i=1;i<=n;i++,l=1-l)
    for(int cw=0;cw<=G;cw++)
    {
        d[l][cw]=d[1-l][cw];
        if(g[i]<=cw)
            d[l][cw]=max(d[l][cw],d[1-l][cw-g[i]]+v[i]);
    }

fout<<d[1-l][G];

    return 0;
}