/*
    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 dp2[2][10000];
void ghiozdan_2linii()
{
    for (int i = 0; i <= G; i++)
        dp2[0][i] = dp2[1][i] = 0;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= G; j++)
        {
            dp2[1][j] = dp2[0][j];
            if (j >= g[i] && p[i] + dp2[0][j - g[i]] > dp2[0][j])
                dp2[1][j] = p[i] + dp2[0][j - g[i]];
        }
        for (int j = 1; j <= G; j++)
            dp2[0][j] = dp2[1][j];
    }
}

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

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

    ghiozdan_2linii();
    int max = 0;
    for (int i = 1; i <= G; i++)
        if (dp2[0][i] > max)
            max = dp2[0][i];
    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;
}