#include <fstream>

using namespace std;

const int Gmax = 10000;

int dp[2][Gmax + 1];

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

    int n, G, w, p;

    fin >> n >> G;

    for(int i = 0; i < n; i++){
        fin >> w >> p;

        for(int j = 0; j <= G; j++){
            dp[i & 1][j] = dp[(i - 1) & 1][j];

            if(w <= j){
                dp[i % 2][j] = max(dp[(i - 1) & 1][j], dp[(i - 1) & 1][j - w] + p);
            }
        }
    }

    fout << dp[!(n & 1)][G];

    return 0;
}