#include <fstream>
using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
/*
top down - recursiva + memoizare\
bootom up - iterativa
*/

struct t_object
{
    int greutate;
    int profit;
};

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

t_object objs[MAX_N];

int dp[MAX_N][MAX_G];
/// dp(idx, capacitate);
/// fiind global, toate valorile matricei sunt deja
/// intializate cu 0

int main()
{
    int nr_elemente;
    int gmax;
    fin >> nr_elemente >> gmax;
    for (int i = 1; i <= nr_elemente; i++)
    {
        int greutate;
        int profit;
        fin >> greutate >> profit;
        t_object obj = {greutate, profit};

        objs[i] = obj;
    }

    /// cazul in care idx == 0 este deja acoperit din moment ce
    /// matricea a fost declarata global

    /// cazul in care greutate == 0 este deja acoprit
    /// din moment ce a fost declarat global

    for(int idx = 1; idx <=  nr_elemente; idx++)
    {
        for(int g = 1; g <= gmax; g++)
        {
            t_object obj = objs[idx];
            if(obj.greutate > g)
            {
                /// nu are loc in ghiozdan
                dp[idx][g] = dp[idx - 1][g];
            }
            else{
                /// are loc in ghiozdan

                ///consideram doua cazuri
                /// cazul 1- il punem in ghiozdan
                int profit1 = dp[idx - 1][g];

                /// cazul 2 - il punem in ghiozdan
                int profit2 = obj.profit + dp[idx - 1][g - obj.greutate];

                dp[idx][g] = max(profit1, profit2);
            }
        }
    }
    fout << dp[nr_elemente][gmax];
    return 0;
}