#include <bits/stdc++.h>

using namespace std;

/// best[i][j] = val max obtinuta din primele i obiecte
/// obttinand greutatea j
/// best[i][j] = best[i-1][j], daca obiectul i nu s-a ales
///              best[i-1][j - g[i]] + v[i], daca am ales obiectul i

int n, G;
int g[5005], v[5000];
int dp[2][5005];

void Citire()
{
    int i;
    ifstream fin("rucsac.in");
    fin >> n >> G;
    for(i = 1; i <= n; i++)
        fin >> g[i] >> v[i];
    fin.close();
}

void Rucsac()
{
    int i, j, L, vmax;
    L = 1;
    for(i = 1; i <= n; i++)
    {
        L = 1 - L;
        for(j = 0; j <= G; j++)
        {
            dp[L][j] = dp[1 - L][j];
            if(j >= g[i]) dp[L][j] = max(dp[1 - L][j - g[i]] + v[i], dp[L][j]);
        }
    }
    vmax = dp[L][0];
    for(i = 1; i <= G; i++)
        vmax = max(vmax, dp[L][i]);
    ofstream fout("rucsac.out");
    fout << vmax << "\n";
    fout.close();
}

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