#include <fstream>

using namespace std;

ifstream cin("rucsac.in");
ofstream cout("rucsac.out");

const int NMAX = 5e3 + 5;

int dp[NMAX];
int w[NMAX], p[NMAX];

int solve(int n, int g)
{
    int s = 0;
    for (int i = 1; i <= n; i++)
    {
        for (int j = g - w[i]; j >= 0; j--)
        {
            if (dp[j] != 0 || j == 0)
                dp[j + w[i]] = max(dp[j + w[i]], dp[j] + p[i]);
        }
    }
    int m = 0;
    for (int i = 0; i <= g; i++)
        m = max(m, dp[i]);
    return m;

}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n, g, i;
    cin >> n >> g;
    for (i = 1; i <= n; i++)
        cin >> w[i] >> p[i];
    cout << solve(n, g);
    return 0;
}