// rucsac.cpp : This file contains the 'main' function. Program execution begins and ends there.
//

#include <fstream>

using namespace std;

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

const int nMax = 5001;
const int kMax = 10001;

int n, k;
int v[nMax], g[nMax];
int best[nMax][kMax];
/*
    * best [i][j] = suma valorilor din primele `i` obiecte avand greutatea `j`
    * daca nu iau obiectul i : dp[i][j] = dp[i - 1][j]
    * daca iau obiectul i : dp[i][j] = dp[i - 1][j - g[i]] + v[i]
*/



void Citire() {
    fin >> n >> k;
    for (int i = 1; i <= n; i++)
        fin >> g[i] >> v[i];
        
}

void Rucsac()
{
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= k; j++) {
            best[i][j] = best[i - 1][j];
            if (j >= g[i]) best[i][j] = max(best[i][j], best[i - 1][j - g[i]] + v[i]);
        }
    }
    int ans = best[n][0];
    for (int i = 1; i <= k; i++)
        if (ans < best[n][i])ans = best[n][i];
    fout << best[n][k];
}

int main()
{
    Citire();
    Rucsac();
}

// Run program: Ctrl + F5 or Debug > Start Without Debugging menu
// Debug program: F5 or Debug > Start Debugging menu

// Tips for Getting Started: 
//   1. Use the Solution Explorer window to add/manage files
//   2. Use the Team Explorer window to connect to source control
//   3. Use the Output window to see build output and other messages
//   4. Use the Error List window to view errors
//   5. Go to Project > Add New Item to create new code files, or Project > Add Existing Item to add existing code files to the project
//   6. In the future, to open this project again, go to File > Open > Project and select the .sln file