#include <fstream>
#include <vector>

using namespace std;

int main()
{
    ifstream fin("rucsac.in");
    ofstream fout("rucsac.out");

    int n, capacitate;
    fin >> n >> capacitate;

    int gmax = 0, rez = 0;
    vector<int> profit_maxim(capacitate + 1, 0);
    profit_maxim[0] = 1;

    while (n--) {
        int val, g;
        fin >> g >> val;

        for (int i = gmax; i >= 0; --i) {
            if (i + g <= capacitate && profit_maxim[i] > 0) {
                profit_maxim[i + g] = max(profit_maxim[i + g], profit_maxim[i] + val);
                rez = max(rez, profit_maxim[i + g] - 1);
                gmax = max(gmax, i + g);
            }
        }
    }

    fout << rez;
    return 0;
}