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

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

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

    for (int i = 1; i <= n; ++i)
    {
        for (int k = 0; k <= capacity; ++k)
            bestValue[0][k] = bestValue[1][k];

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

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

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