#include <cstdio>
#include <algorithm>
using namespace std;

const int nmax=5000,grmax=10000;
int n,gmax,x,y,z,g,profmax;
int prof[grmax];
struct w{int g; int c;};
struct w v[nmax];
bool asa(w i,w j) {return(i.g<j.g);}
bool a[grmax][nmax];

void citire()
{
    freopen("rucsac.in","r",stdin);
    freopen("rucsac.out","w",stdout);
    scanf("%d %d",&n,&gmax);
    for(x=1;x<=n;x++)
        scanf("%d %d",&v[x].g,&v[x].c);
}

int main()
{
    citire();
    sort(v+1,v+n+1,asa);
    for(x=1;x<=gmax;x++)
    {
        for(y=1;y<=n;y++)
        {
            if (v[y].g>x) break;

            g=v[y].g;
            if ((prof[x-g] || x==g) && prof[x]<prof[x-g]+v[y].c && !a[x-g][y])
            {
                prof[x]=prof[x-g]+v[y].c;
                for(z=1;z<=n;z++) a[x][z]=a[x-g][z];
                a[x][y]=1;
            }
        }

        if (prof[x]>profmax) profmax=prof[x];
    }
    printf("%d\n",profmax);
}