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

using namespace std;

ifstream input("rucsac.in");
ofstream output("rucsac.out");

int main()
{
    int N, G;
    input >> N >> G;
    vector<int> weight(N);
    vector<int> profit(N);
    vector<vector<int>> D(2, vector<int>(G+1, 0));

    for(int i = 0; i < N; i++){
        input >> weight[i] >> profit[i];
    }
    for(int i = 1; i <= N; i++){
        for(int j = 0; j <= G; j++){
            D[1][j] = D[0][j];
            if(j - weight[i-1] >= 0 && D[1][j] < (D[0][j-weight[i-1]] + profit[i-1])){
                D[1][j] = D[0][j-weight[i-1]] + profit[i-1];
            }
        }
        for(int j = 0; j <= G; j++){
            D[0][j] = D[1][j];
        }
    }

    output << D[1][G];
    return 0;
}