#include <bits/stdc++.h>

using namespace std;

ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
int n, G, sol;
int g[5005], v[5005];
int dp[2][5005];
int main()
{
    int i, j, ind;
    fin >> n >> G;
    for (i = 1; i <= n; i++)
        fin >> g[i] >> v[i];

    ind = 1;
    for (i = 1; i <= n; i++, ind ^= 1)
    {
        for (j = G; j >= g[i]; j--)
        {
            if (dp[ind ^ 1][j - g[i]] > 0 or j - g[i] == 0)
                dp[ind][j] = max(dp[ind ^ 1][j], dp[ind ^ 1][j - g[i]] + v[i]);
            else
                dp[ind][j] = dp[ind ^ 1][j];
        }
    }
    ind ^= 1;
    for (i = 1; i <= G; i++)
        sol = max(sol, dp[ind][i]);
    fout << sol << "\n";

    return 0;
}