#include <cstdio>
#include <cstring>
using namespace std;

const int GMAX = 10000;
int d[2 * GMAX + 5];

int minim(int a, int b)
{
    if (a < b)
        return a;
    return b;
}

int main()
{
    freopen("rucsac.in", "r", stdin);
    freopen("rucsac.out", "w", stdout);
    int n, m, g, p, maxim, ans;

    scanf("%d %d", &n, &m);
    memset(d, 0, sizeof(d));
    d[0] = 1; maxim = ans = 0;
    for (int nr = 1; nr <= n; ++nr)
    {
        scanf("%d %d", &g, &p);
        for (int i = minim(maxim, m - g); i >= 0; --i)
            if (d[i] != 0)
                if (d[i + g] < d[i] + p)
                {
                    d[i + g] = d[i] + p;
                    if (d[i] + p > ans)
                        ans = d[i] + p;
                }
        maxim += g;
        if (maxim > m)
            maxim = m;
    }
    printf("%d\n", ans - 1);
    return 0;
}