#include <fstream>
#include <cstdio>
#define DMAX 5010
#define NMAX 10010

using namespace std;

FILE*fin=fopen("rucsac.in", "r");
ofstream fout("rucsac.out");

int gmax, n;
int g[DMAX], p[DMAX];
int pmax[2][NMAX];

void citire();
void pd();

int main()
{
    citire();
    pd();

    return 0;
}

void citire()
{
    int i;
    fscanf(fin, "%d%d", &n, &gmax);
    for(i=1;i<=n;i++)
    {
        fscanf(fin, "%d%d", &g[i], &p[i]);
    }
}

void pd()
{
    int i, gt;
    for(gt=1;gt<=gmax;gt++)
        if(g[1]<=gt)
            pmax[1][gt]=p[1];

    for(i=2;i<=n;i++)
        for(gt=1;gt<=gmax;gt++)
        {
            pmax[i%2][gt]=pmax[(i-1)%2][gt];
            if(g[i]<gt && pmax[(i-1)%2][gt-g[i]]+p[i]>pmax[i%2][gt])
                pmax[i%2][gt]=pmax[(i-1)%2][gt-g[i]]+p[i];
        }
    fout<<pmax[n%2][gmax]<<'\n';
}