#include<fstream>
using namespace std;
ifstream in("rucsac.in");
ofstream out("rucsac.out");
const int NMax = 5000;
const int GMax = 10000;

int N,G,W[NMax+5],P[NMax+5],DP[2][GMax+5];

void ReadSolvePrint() {
    in >> N >> G;
    for (int i = 1; i <= N; i++)
        in >> W[i] >> P[i];

    /*for (int i = 1; i <= N; i++)
        for (int j = 0; j <= G; j++) {
            DP[i][j] = DP[i-1][j];
            if(j-W[i] >= 0)
                DP[i][j] = max(DP[i][j], DP[i-1][j-W[i]] + P[i]);
        }

    out << DP[N][G];*/
    int l = 0;
    for (int i = 1; i <= N; i++,l=1-l)
        for (int j = 0; j <= G; j++) {
            DP[l][j] = DP[1-l][j];
            if(j-W[i] >= 0)
                DP[l][j] = max(DP[l][j], DP[1-l][j-W[i]] + P[i]);
        }
    out << DP[1-l][G];

}

int main() {
    ReadSolvePrint();
}