#include <iostream>
#include <fstream>

using namespace std;

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

const int NMax = 5 * 1e3, GMax = 1e4;

int n, g;
int w[NMax + 5], p[NMax + 5], dp[5][GMax + 5];

void Read(){
    fin >> n >> g;
    for (int i = 1; i <= n; i++)
        fin >> w[i] >> p[i];
}

void DP(){
    bool ind = 1;
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= g; j++){
            if (j >= w[i])
                dp[ind][j] = max(dp[!ind][j], dp[!ind][j - w[i]] + p[i]);
            else
                dp[ind][j] = dp[!ind][j];
        }
        ind = !ind;
    }
}

void Print(){
    fout << dp[n % 2][g] << '\n';
}

int main(){
    Read();
    DP();
    Print();
    return 0;
}