#include <fstream>
using namespace std;

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

const int MAX_N=5001, MAX_G=10000;

struct t_object
{
    int greutate;
    int profit;
};

int memo[MAX_N][MAX_G];

int dp_profit(int idx, int capacitate, t_object objs[])
{
    if(idx==0) return 0;
    if (capacitate==0) return 0;
    if(memo[idx][capacitate]!=0)
        return memo[idx][capacitate];
    if(objs[idx].greutate>capacitate)
    {
        memo[idx][capacitate]=dp_profit(idx-1,capacitate,objs);
        return memo[idx][capacitate];
    }
    //cazul 1 - nu luam obiectul
    int profit1=dp_profit(idx-1,capacitate,objs);

    //cazul 2 - luam obiectul
    int new_capacitate=capacitate-objs[idx].greutate;
    int profit2=objs[idx].profit+dp_profit(idx-1,new_capacitate,objs);

    memo[idx][capacitate]=max(profit1,profit2);
    return memo[idx][capacitate];
}

int main()
{
    int nr_elem, max_gr;
    t_object objs[MAX_N];
    fin>>nr_elem>>max_gr;
    for(int i=1;i<=nr_elem;i++)
    {
        int greutate, profit;
        fin>>greutate>>profit;
        t_object obj={greutate,profit};
        objs[i]=obj;
    }
    fout<<dp_profit(nr_elem,max_gr,objs);
    return 0;
}