#include <iostream>
#include <fstream>

using namespace std;

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

struct{
    int g, val;
}obiect[5001];

int gMax, n;
int costMax[5001][10001];

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

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


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