#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 stocat[5001][10001];

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

void initializare(){
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= gMax; j++){
            stocat[i][j] = -1;
        }
    }
}

int castigMaxim(int r, int c){
    if(stocat[r][c] != -1){
        return stocat[r][c];
    }
    int rezultat;
    if(r == 0 || c == 0){
        rezultat = 0;
    }
    int temp1 = castigMaxim(r - 1, c);
    rezultat = temp1;
    if(obiect[r].g <= c){ // obiectul ar incapea in rucsac
        int temp2 = obiect[r].val + castigMaxim(r - 1, c - obiect[r].g);
        rezultat = max(temp1, temp2);
    }
    stocat[r][c] = rezultat;
    return rezultat;
}


int main() {
    citire();
    initializare();
    out << castigMaxim(n, gMax);
    return 0;
}