#include <iostream>
#include <fstream>

using namespace std;
//ifstream fin("rucsac.in");
//ofstream fout("rucsac.out");

const int MAX_N=5001;
const int MAX_G=10000;

struct t_object
{
    int greutate;
    int profit;
};

int memo[MAX_N][MAX_G];
int dp_profit(int idx, int cap, t_object obj[])
{
    if(idx==0)
        return 0;
    if(cap==0)
        return 0;
    if(memo[idx][cap] != 0)
        return memo[idx][cap];
    if(obj[idx].greutate>cap)
    {
        memo[idx][cap]=dp_profit(idx-1, cap, obj);
        return memo[idx][cap];
    }

    int profit1 = dp_profit(idx-1, cap, obj);
    int profit2 = obj[idx].profit + dp_profit(idx-1, cap-obj[idx].greutate, obj);
    memo[idx][cap]=max(profit1, profit2);
    return memo[idx][cap];

}


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

    return 0;
}

//6 10
//3 7
//3 4
//1 2
//1 9
//2 4
//1 5