#include <cstdio>
#include <algorithm>

using namespace std;

/// https://www.infoarena.ro/problema/rucsac
int lastLine[10001], curLine[10001];
int n, g, i;

int weight[5001], profit[5001];

int maxProfit(int lastLine[], int curLine[], int n, int g)
{
    if (n==0)
        return lastLine[g];
    else
    {
        for (i=1; i<=g; i++)
        {
            if (weight[n] <= i)
                curLine[i] = max(lastLine[i], profit[n] + lastLine[i-weight[n]]);
            else
                curLine[i] = lastLine[i];
        }
        return maxProfit(curLine, lastLine, n-1, g);
    }
}

int main() {
    freopen("rucsac.in", "r", stdin);
    freopen("rucsac.out", "w", stdout);

    scanf("%d%d", &n, &g);
    for (i=1; i<=n; i++)
        scanf("%d%d", &weight[i], &profit[i]);

    for (i = weight[n]; i<=g; i++)
        curLine[i] = profit[n];

    printf("%d", maxProfit(lastLine, curLine, n, g));

    return 0;
}