#include <bits/stdc++.h>

#define fs fscanf
#define fp fprintf

using namespace std;

FILE *f, *g;

int w[5005], p[5005];

int n, gr, i;
int d[2][10005], cw;

int main()
{
    f = fopen("rucsac.in", "r");
    g = fopen("rucsac.out", "w");

    fs(f, "%d%d", &n, &gr);

    for(i = 1; i <= n; i ++)
    {
        fs(f, "%d%d", &w[i], &p[i]);
    }

    for(i = 1; i <= n; i ++)
    {
        for(cw = 1; cw <= gr; cw ++)
        {
            d[0][cw] = d[1][cw];
            if(w[i] <= cw)
                d[1][cw] = max(d[0][cw], d[0][cw-w[i]] + p[i]);
        }
    }

    fp(g, "%d\n", d[1][gr]);

    fclose(f);
    fclose(g);
    return 0;
}