#include <fstream>
#define NMAX 4001
#define GMAX 5001

using namespace std;

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

int n, gmax;
int greutate[NMAX];
int valoare[NMAX];

int dp[NMAX][GMAX];

void citeste()
{
    fin >> n >> gmax;
    for (int i = 1; i <= n; ++i)
        fin >> greutate[i] >> valoare[i];
}

int Knapsack()
{
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= gmax; j++)
        {
            if (j < greutate[i])
                dp[i][j] = dp[i-1][j];
            else
                dp[i][j] = max(valoare[i] + dp[i-1][j-greutate[i]] , dp[i-1][j]);
        }
    }
    return dp[n][gmax];
}

int main()
{
    citeste();
    fout << Knapsack();

    fin.close();
    fout.close();
}