#include<cstdio>
#define NMAX 5001
#define LMAX 10001
using namespace std;

int n, G, g[NMAX], p[NMAX];
int D[2][LMAX], lc, lp;

inline int maxim(int a, int b)
{
    if(a > b) return a;
    return b;
}

int main()
{
    int i, j;
    FILE *fin, *fout;
    fin = fopen("rucsac.in","r");
    fout = fopen("rucsac.out","w");
    fscanf(fin,"%d%d",&n,&G);
    for(i=1; i<=n; i++)
        fscanf(fin,"%d%d",&g[i],&p[i]);
    fclose(fin);
    lc = 1;
    for(i=1; i<=n; i++)
    {
        for(j=0; j<=G; j++)
            if(j < g[i])
                D[lc][j] = D[lp][j];
            else
                D[lc][j] = maxim(D[lp][j], D[lp][j-g[i]] + p[i]);
        lc = 1-lc;
        lp = 1-lp;
    }
    fprintf(fout,"%d\n",D[lp][G]);
    fclose(fout);
    return 0;
}