#include <iostream>
using namespace std;

const int NMAX = 5e3, GMAX = 1e4;
int N, G, W[NMAX + 1], P[NMAX + 1];
int dp[2][GMAX + 1]; // dp[i][j] profitul maxim pentru greutate mai mica sau egala cu j dintre primele i obiecte

void read()
{
    freopen("rucsac.in", "r", stdin);
    cin >> N >> G;
    for (int i = 1; i <= N; i++)
    {
        cin >> W[i] >> P[i];
    }
}

int main()
{
    read();

    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= G; j++)
        {
            if (j < W[i])
            {
                dp[(i & 1)][j] = dp[(i & 1) ^ 1][j];
                continue;
            }
            dp[(i & 1)][j] = max(dp[(i & 1) ^ 1][j], dp[(i & 1) ^ 1][j - W[i]] + P[i]);
        }
    }

    freopen("rucsac.out", "w", stdout);
    cout << dp[N & 1][G];
    return 0;
}