#include <iostream>
#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 memo[MAX_N][MAX_G];
int dp_profit(int idx,int capacitate, t_object objs[],int memo[][MAX_G])
{
    if(idx==0)
        return 0;
    if(capacitate==0)
        return 0;
    if(memo[idx][capacitate] !=0)
        return memo[idx][capacitate];
    t_object curr_obj=objs[idx];
    if(curr_obj.weight > capacitate)
    {
         memo[idx][capacitate]=dp_profit(idx-1,capacitate,objs,memo);
         return memo[idx][capacitate];
    }

    // cazul 1 nu punem obiectul

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

    //cazul2 punem obiectul

    int profit2= objs[idx].profit+dp_profit(idx-1,capacitate-curr_obj.weight,objs,memo);
    memo[idx][capacitate]= max(profit1,profit2);
    return memo[idx][capacitate];
}

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;
        fin>>curr_profit;
        t_object obiect={curr_greutate,curr_profit};
        objs[i]=obiect;
    }

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