#include <fstream>

#define Wmax 10010

using namespace std;

int N, G, Solution, DP[Wmax];

int main() {

    int i, j, weight, profit;
    ifstream in("rucsac.in");
    ofstream out("rucsac.out");

    in >> N >> G;

    DP[0] = 1;

    for(i = 1; i <= N; i++) {

        in >> weight >> profit;

        for(j = min(Wmax - 1, G - weight); j >= 0; j--)
            if(DP[j] && DP[j + weight] < DP[j] + profit)
                DP[j + weight] = DP[j] + profit;

        }

    for(i = 0; i <= G; i++)
        if(DP[i] > Solution)
            Solution = DP[i];

    out << (Solution - 1) << '\n';

    in.close();
    out.close();

    return 0;

}