#include <cstdio>

using namespace std;

int gr[10001];
int p[10001];
int c[10001];
int main()
{
    freopen("rucsac.in", "r", stdin);
    freopen("rucsac.out", "w", stdout);

    int n, g;
    scanf("%d%d", &n, &g);
    int lim = 0;
    int i, j;
    for (i = 1; i <= n; ++i)
        scanf("%d%d", &gr[i], &p[i]);
    for (i = 1; i <= n; ++i)
    {
        for (j = lim; j >= 0; --j)
            if ((j == 0 && c[j] + p[i] > c[j + gr[i]]) || (c[j] != 0 && c[j] + p[i] > c[j + gr[i]]))
            {
                c[j + gr[i]] = c[j] + p[i];
            }
        lim = lim + gr[i];
    }
    int maxim = 0;
    for (i = 0; i <= g; ++i)
        if (c[i] > maxim)
            maxim = c[i];
    printf("%d\n", maxim);
    return 0;
}