#include <fstream>
#include <algorithm>
using namespace std;

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

const int MAX_N = 5000;
const int MAX_C = 10000;
int V[MAX_N][MAX_C];

int comp(int i, int j, int *d, int *v)
{
    if (i == 0 || j == 0)
    {
        V[i][j] = 0;
        return V[i][j];
    }
    else
    {
        if (V[i][j] != -1)
        {
            return V[i][j];
        }
        else
        {
            if (j < d[i])
            {
                V[i][j] = comp(i - 1, j, d, v);
            }
            else
            {
                V[i][j] = max(comp(i - 1, j, d, v), comp(i - 1, j - d[i], d, v) + v[i]);
            }
            return V[i][j];
        }
    }
}

int main()
{
    int C, N;
    fin >> N >> C;
    int d[MAX_N], v[MAX_N];
    for (int i = 1; i <= N; i++)
    {
        fin >> d[i] >> v[i];
    }

    for (int i = 0; i <= N; i++)
    {
        for (int j = 0; j <= C; j++)
        {
            V[i][j] = -1;
        }
    }

    int result = comp(N, C, d, v);
    fout << result << endl;

    return 0;
}