#include <fstream>

using namespace std;

int dp[2][10005];
int w[5005], p[5005];
int n, G;

void Read ()
{
    ifstream fin ("rucsac.in");
    fin >> n >> G;
    for (int i = 1; i <= n; i++)
        fin >> w[i] >> p[i];
}

void DP ()
{
    int lin = 0;
    dp[lin][w[1]] = p[1];
    for (int i = 2; i <= n; i++)
    {
        for (int j = 1; j <= G; j++)
        {
            int M = dp[lin][j];
            if (j >= w[i] && M < dp[lin][j - w[i]] + p[i])
                M = dp[lin][j - w[i]] + p[i];
            dp[1 - lin][j] = M;
        }
        lin = 1 - lin;
    }
    ofstream fout ("rucsac.out");
    int ans = 0;
    for (int i = 1; i <= G; i++)
        ans = max(ans, dp[1][i]);
    fout << ans << "\n";
}

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