#include <fstream>
#include <cstring>

#define Wmax 10010
#define previous ((i & 1) ^ 1)
#define current (i & 1)

using namespace std;

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

int main() {

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

    in >> N >> G;

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

        in >> weight >> profit;

        memset(DP[current], 0, sizeof(DP[current]));

        for(j = 0; j <= G; j++) {

            DP[current][j] = DP[previous][j];

            if(weight <= j)
                DP[current][j] = max(DP[current][j], DP[previous][j - weight] + profit);
        }
    }

    out << DP[N & 1][G] << '\n';

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

    return 0;

}