#include <stdio.h>
#include <algorithm>
using namespace std;

#define MAXN 5000
#define MAXG 10000

int d[3][MAXG];

struct obiecte
{
    int w, p;
}v[MAXN];

int main()
{
    FILE *fin,*fout;

    fin = fopen("rucsac.in","r");
    fout = fopen("rucsac.out","w");

    int n, g;

    fscanf(fin, "%d%d", &n , &g);

    for(int i = 1; i <= n; i++)
        fscanf(fin,"%d%d", &v[i].w, &v[i].p);


    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= g; j++)
        {
            d[2][j] = d[1][j];
            if(v[i].w <= j)
                d[2][j] = max(d[2][j], d[1][j - v[i].w] + v[i].p);
        }
        for(int j = 1; j <= g; j++)
        {
            d[1][j] = d[2][j];
            d[2][j] = 0;
        }
    }

    fprintf(fout, "%d", d[1][g]);

    return 0;
}