#include <fstream>
#include <cmath>

using namespace std;

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

///1 ≤ N ≤ 5000
///1 ≤ G ≤ 10000
///0 ≤ Wi, Pi ≤ 10000

const int MAX_N = 5001;
const int MAX_G = 10001;

int objs[MAX_N], memo[MAX_N][MAX_G];

struct t_object{
    int weight;
    int profit;
};


int dp_profit(int idx, int capacitate, t_object objs[], int memo[][MAX_G]){

    if(idx == 0){///nu mai avem obiecte de luat in considerare
        return 0;
    }

    if(capacitate == 0){
        return 0;
    }

    if(memo[idx][capacitate] != 0)
        return memo[idx][capacitate];

    t_object curr_object = objs[idx];

    if(curr_object.weight > capacitate){///nu putem pune obiectul in ghiozdan
        return dp_profit(idx - 1, capacitate, objs, memo);
    }

    ///putem pune obiectul in ghiozdan, verificam daca este mai profitabil sa il punem sau nu
    ///cazul 1 - nu punem obiectul in ghiozdan
    int profit1 = dp_profit(idx - 1, capacitate, objs, memo);

    ///cazul 2 - punem obiectul in ghiozdan
    int profit2 = curr_object.profit + dp_profit(idx - 1, capacitate - curr_object.weight, objs, memo);

    return max(profit1, profit2);

}



int main(){

    int n, greutate;

    t_object objs[MAX_N + 1];

    cin >> n >> greutate;

    for(int i = 1; i <= n; i++){

        int curr_weight, curr_profit;

        cin >> curr_weight >> curr_profit;

        t_object obiect = {curr_weight, curr_profit};

        objs[i] = obiect;
    }

    cout << dp_profit(n, greutate, objs, memo);

    return 0;
}