#include <iostream>
#include <fstream>

using namespace std;

const int M = 10001;
const int N = 5001;

ifstream fcin("rucsac.in");
ofstream fcout("rucsac.out");

short n, capacity;
short weights[M], values[M], bestValue[N][M];

short max(short a, short b)
{
    if (a > b)
        return a;
    return b;
}

int main()
{
    fcin >> n >> capacity;
    for (short i = 0; i < n; ++i)
        fcin >> weights[i] >> values[i];

    for (short i = 1; i <= n; ++i)
    {
        short idx = i - 1;
        for (short j = 0; j <= capacity; ++j)
        {
            ///including the item
            if (weights[idx] + j <= capacity)
                bestValue[i][weights[idx] + j] = max(bestValue[i - 1][j] + values[idx], bestValue[i][weights[idx] + j]);

            ///not including the item
            bestValue[i][j] = max(bestValue[i][j], bestValue[i - 1][j]);
        }
    }
    fcout << bestValue[n][capacity];
}