#include <iostream>
#include <fstream>

using namespace std;

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

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

int gMax, n;

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

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


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