#include <bits/stdc++.h>

using namespace std;

ifstream f("rucsac.in");
ofstream g("rucsac.out");


struct rucsac
{
    int w,p;
}v[5010];


int n,G,i,greut,d[2][10100];

int main()
{
    f>>n>>G;
    for(i=1;i<=n;i++)
    {
        f>>v[i].w>>v[i].p;
    }

    for(i=1;i<=n;i++)
    {



      for(greut=0;greut<=G;greut++)
      {
          if(greut>=v[i].w)
          {
              d[2][greut]=max((d[1][greut-v[i].w]+v[i].p),d[1][greut]);
          }
          else
          {
              d[2][greut]=d[1][greut];
          }
      }


      for(greut=0;greut<=G;greut++)d[1][greut]=d[2][greut];

    }

    g<<d[1][G];

    return 0;
}