#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;
    DP[0][0] = 1;

    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[previous][j - weight] != 0)
                DP[current][j] = max(DP[current][j], DP[previous][j - weight] + profit);
        }
    }

    for(i = G; i > 0; i--)
        if(DP[N & 1][i] != 0) {
            out << (DP[N & 1][i] - 1) << '\n';
            break;
        }

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

    return 0;

}