/*
    G = greutate rucsac
    n obiecte
    g[1 .. n] = greutate obiect i
    p[1 .. n] = pret obiect i

    dp[i][j] = profitul maxim obtinut din primele i obiecte ce au greutatea j
    dp[0][i] = 0, i = 0 .. n - 1
    dp[i][j] = max { d[i - 1][j], p[i] + d[i - 1][j - g[j]] }    
                      nu pui   ,       pui obiectul i(daca mai incape)
    solutia: dp[n][j] j = 0 .. G -> profitul maxim obtinut din cele n obiecte ce pot sa aiba orice greutate
*/

#include <iostream>
#include <fstream>

using namespace std;

ifstream f("rucsac.in");
ofstream g_("rucsac.out");

int n, G;// = 6, G = 10;
int p[5000], g[5000];
int dp[5000][10000];

int ghiozdan(int i, int j)
{
    if (dp[i][j] != -1)
        return dp[i][j];
    if (i == 0)
        return dp[i][j] = 0;

    dp[i][j] = ghiozdan(i - 1, j); // nu punem obiectul
    // daca incape obiectul si daca aduce un profit mai mare il punem
    if(j >= g[i] && ghiozdan(i - 1, j) < p[i] + ghiozdan(i - 1, j - g[i]))
        dp[i][j] = p[i] + ghiozdan(i - 1, j - g[i]);
    return dp[i][j];
}

void ghiozdan_it()
{
    for (int i = 0; i <= G; i++)
        dp[0][i] = 0;
    for(int i = 1; i <= n; i++)
        for (int j = 1; j <= G; j++)
        {
            dp[i][j] = dp[i - 1][j];
            if (j >= g[i] && p[i] + dp[i - 1][j - g[i]] > dp[i - 1][j])
                dp[i][j] = p[i] + dp[i - 1][j - g[i]];
        }
}

int main()
{
    f >> n >> G;
    for (int i = 1; i <= n; i++) 
        f >> g[i] >> p[i];
    for (int i = 0; i <= n; i++)
        for (int j = 0; j <= G; j++)
            dp[i][j] = -1;

    ghiozdan(n, G);
    //ghiozdan_it();
    int max = 0;
    for (int j = 1; j <= G; j++)
        if (dp[n][j] > max)
            max = dp[n][j];
    g_ << max;
    //cout << "Profitul maxim este " << max << "\n\n";

    /*for (int i = 0; i <= n; i++)
    {
        for (int j = 0; j <= G; j++)
            cout << dp[i][j] << " ";
        cout << "\n";
    }*/
    return 0;
}