#include <fstream>

using namespace std;
ifstream f("rucsac.in");
ofstream g("rucsac.out");
struct obiecte
{
    int w,p;
}v[5001];
int n,gg,i,l,q,d[3][10001],gr;
int main()
{
   f>>n>>gg;
   for(i=1;i<=n;i++)
    f>>v[i].w>>v[i].p;
   d[0][v[1].w]=v[1].p;
   l=1;
   for(q=2;q<=n;q++)
    {
        for(gr=1;gr<=gg;gr++)
        {
            if(gr>=v[q].w)d[l][gr]=max(d[1-l][gr],d[1-l][gr-v[q].w]+v[q].p);
             else d[l][gr]=d[1-l][gr];
        }
    l=1-l;
    }
    g<<d[1-l][gg];
    return 0;
}