#include <bits/stdc++.h>
#define nmax 5005
#define gmax 10005

using namespace std;

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

int n,G,g[nmax],v[nmax],dp[4][gmax];

void Citire()
{
    fin >> n >> G;
    for(int i = 1; i <= n; i++)
        fin >> g[i] >> v[i];
}

void Dinamica()
{
    int i,j;
    for(i = g[1]; i <= G; i++)
        dp[1][i] = v[1];
    for(i = 2; i <= n; i++)
    {
        for(j = 1; j <= G; j++)
            if(g[i] > j) dp[2][j] = dp[1][j];
            else dp[2][j] = max(dp[1][j],dp[1][j-g[i]] + v[i]);
        for(j = 1; j <= G; j++)
        {
            dp[1][j] = dp[2][j];
            dp[2][j] = 0;
        }
    }
}

void Afisare()
{
    fout << dp[1][G] << "\n";
}

int main()
{
    Citire();
    Dinamica();
    Afisare();
    fin.close();
    fout.close();
    return 0;
}