#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

ifstream f("rucsac.in");
ofstream g("rucsac.out");

int main()
{
    int n, g;

    vector<pair<int, int>> data;

    f >> n >> g;

    vector<vector<int>> cmax;

    cmax.resize(n + 2);

    for(int index = 0; index <= n; index++)
        cmax[index].resize(g + 2);

    data.resize(n + 2);

    for(int index = 0; index <= n; index++)
    {
        int x, y;
        f >> x >> y;
        data[index].first = x;
        data[index].second = y;
    }

    for(int index = 0; index <= n; index++)
        for(int index2 = 1; index2 <= g; index2++)
            cmax[index][index2] = 0;

    for(int index = 1; index <= n; index++)
        for(int index2 = 1; index2 <= g; index2++)
        {
            cmax[index][index2] = cmax[index - 1][index2];
            if(data[index].first <= index2 && data[index].second + cmax[index - 1][index2 - data[index].first] > cmax[index - 1][index2])
                cmax[index][index2] = data[index].second + cmax[index - 1][index2 - data[index].first];
        }

    g << cmax[n][g];

    return 0;
}