#include <iostream>
#include <fstream>

using namespace std;

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

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

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

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

    for (int i = 1; i <= n; ++i)
        for (int j = 0; j <= capacity; ++j)
        {
            int totalValue = bestValue[i - 1][j] + values[i];
            int totalWeight = weights[i] + j;

            ///including the item
            if (totalWeight <= capacity)
                bestValue[i][totalWeight] = totalValue;

            ///not including the item
            bestValue[i][totalWeight] = max(bestValue[i][totalWeight], bestValue[i - 1][j]);
        }

    fcout << bestValue[n][capacity];
}