#include <fstream>
using namespace std;

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

const int MAX_N = 5005;
const int MAX_G = 10005;

struct t_object
{
    int weight;
    int profit;
};

int dp_profit(int idx, int capacitate, t_object objs[])
{
    if (idx == 0)
        return 0;

    if(capacitate == 0)
        return 0;

    t_object curr_obj = objs[idx];

    if(curr_obj.weight > capacitate)
    {
        return dp_profit(idx - 1, capacitate, objs);
    }

    ///cazul 1 - nu punem obiectul in ghiozdan

    int profit1 = dp_profit(idx - 1, capacitate, objs);

    ///cazul 2 - punem obiectul in ghiozdan

    int profit2 = curr_obj.profit +dp_profit(idx - 1, capacitate - curr_obj. weight, objs);

    return max(profit1, profit2);
}                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                          ;

int main()
{
    int n, greutate;
    fin >> n >> greutate;
    t_object objs[MAX_N];

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

        fin >> curr_greutate >> curr_profit;

        t_object obiect = {curr_greutate, curr_profit};
        objs[i] = obiect;
    }

    fout << dp_profit(n, greutate, objs);
    return 0;
}