#include <cstdio>
#include <cstring>

using namespace std;

int w[5001], p[5001];
int best[10001];
int n, g;

int main()
{
    freopen("rucsac.in", "r", stdin);
    freopen("rucsac.out", "w", stdout);
    scanf("%d%d", &n, &g);
    for (int i = 0; i < n; i++)
    {
        scanf("%d %d", &w[i], &p[i]);
    }
    memset(best, 0, sizeof(best));
    int s = 0;
    for (int i = 0; i < n; i++)
        for (int j = g - w[i]; j >= 0; j--)
            if (best[j + w[i]] < best[j] + p[i])
            {
                best[j + w[i]] = best[j] + p[i];
                if (best[j + w[i]] > s)
                    s = best[j + w[i]];
            }
    printf("%d", s);
    return 0;
}