#include <iostream>
#include <fstream>

using namespace std;

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

int gMax, n;
int costMax[6000][10100], g[6000], val[6000];

void citire(){
    in >> n >> gMax;
    for(int i = 1; i <= n; i++){
        in >> g[i] >> val[i];
    }
}

int castigMaxim(){
    for(int i = 1; i <= n; i++){
        for(int j = 0; j <= gMax; j++){
            costMax[i][j] = costMax[i - 1][j];
            if(g[i] <= j){
                costMax[i][j] = max(costMax[i][j], costMax[i - 1][j - g[i]] + val[i] );
            }
        }
    }
    return costMax[n][gMax];
}


int main() {
    citire();
    out << castigMaxim();
    return 0;
}