#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[2][MAX_C];

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];
    }

    int currentRow = 0;
    for (int i = 0; i <= N; i++)
    {
        for (int j = C; j > 0; j--)
        {
            if (i == 0 || j == 0)
            {
                V[currentRow][j] = 0;
            }
            else
            {
                if (j < d[i])
                {
                    V[currentRow][j] = V[1 - currentRow][j];
                }
                else
                {
                    V[currentRow][j] = max(V[1 - currentRow][j], V[1 - currentRow][j - d[i]] + v[i]);
                }
            }
        }
        currentRow = 1 - currentRow;
    }

    fout << V[1 - currentRow][C] << endl;

    fin.close();
    fout.close();

    return 0;
}