#include <fstream>

using namespace std;

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

int n, g;
int w[5010], p[5010];
int dp[10010];
int M[10010][5010];
int imax, jmax;

int main()
{
    fin >> n >> g;
    for(int i = 1; i <= n; i++)
    {
        fin >> w[i] >> p[i];
        if(w[i] == 0 && p[i] > dp[0])
        {
            dp[0] = p[i];
            imax = i;
        }
    }
    M[0][imax] = 1;
    for(int i = 1; i <= g; i++)
    {
        dp[i] = dp[i-1];

        for(int j = 1; j <= n; j++)
        {
            if(M[i-1][j]==0)
            {
                if(w[j] <= i && p[j]+dp[i-w[j]] > dp[i] && !M[i-w[j]][j])
                {
                    dp[i]=p[j]+dp[i-w[j]];
                    jmax = j;
                }
            }
        }

        for(int j = 1; j <= n; j++)
        {
            M[i][j] = M[i-w[jmax]][j];
        }
        M[i][jmax] = 1;
    }
    fout << dp[g];
    return 0;
}