#include <fstream>

using namespace std;
ifstream f("rucsac.in");
ofstream g("rucsac.out");
int n,gmax,i,cw,gr[5010],pr[5010],d[2][10010];
int main()
{
    f>>n>>gmax;
    for(i=1;i<=n;i++)
        f>>gr[i]>>pr[i];
    int l=0;
    for(i=1;i<=n;i++,l=1-l)
        for(cw=0;cw<=gmax;cw++)
    {
        d[1-l][cw]=d[l][cw];
              if(gr[i] <= cw)
                d[1-l][cw] = max(d[1-l][cw], d[l][cw - gr[i]] + pr[i]);
    }
    g<<d[l][gmax];

        return 0;
}