#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

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

int N, G;
vector<int> g, p;
vector<vector<int>> dp;

void ReadData();
void Solve();

int main()
{
    ReadData();
    Solve();

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

void ReadData()
{
    fin >> N >> G;

    g = p = vector<int>(N + 1);
    for (int i = 1; i <= N; ++i)
    {
        fin >> g[i] >> p[i];
    }
}

void Solve()
{
    dp = vector<vector<int>>(2, vector<int>(G + 1));
    dp[0][0] = 0;   // Initilaizare

    // Recurenta
    int lc = 1, lp = 0;
    for (int i = 1; i <= N; ++i, lc = !lc, lp = !lp)
    {
        for (int j = 0; j < g[i]; ++j)
            dp[lc][j] = dp[lp][j];
        for (int j = g[i]; j <= G; ++j)
            dp[lc][j] = max(dp[lp][j], dp[lp][j - g[i]] + p[i]);
    }

    // Rezultatul final
    int res = 0;
    for (int j = 0; j <= G; ++j)
        if (dp[lp][j] > res)       // lp in loc de lc pentru ca linia curenta e schimbata inca odata iniante sa ies din for
        {
            res = dp[lp][j];
        }
    
    fout << res << '\n';
}