#include <bits/stdc++.h>

using namespace std;

ifstream fin ("rucsac.in");
ofstream fout ("rucsac.out");

const int NMAX = 5000 + 5;
const int GMAX = 10000 + 5;

int dp[2][GMAX], N , G, p[NMAX], g[NMAX];

void read()
{
    fin >> N >> G;

    for (int i = 1; i <= N; ++i)
        fin >> g[i] >> p[i];
}

void DP()
{
    for (int i = 1; i <= N; ++i)
    {
        for (int j = 1; j <= G; ++j)
        {
            if (j - g[i] >= 0)
                dp[i & 1][j] = max(dp[(i - 1) & 1][j], dp[(i - 1) & 1][j - g[i]] + p[i]);
            else
                dp[i & 1][j] = dp[(i - 1) & 1][j];
        }
    }

    fout << dp[N & 1][G];
}


int main()
{
    read();
    DP();
    return 0;
}