#include <fstream>

using namespace std;

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

const int MAX_N = 5001;
const int MAX_G = 1000;

struct t_object
{
    int greutate;
    int profit;
};

int main()
{
    int nr_elem;
    int gmax;
    t_object objs[MAX_N];

    fin >> nr_elem >> gmax;

    for(int i=1; i<=nr_elem; i++)
    {
        int greutate;
        int profit;

        fin >> greutate >> profit;
        t_object obj = {greutate, profit};

        objs[i] = obj;
    }

    for(int idx=1; idx<=nr_elem; idx++)
        for(int g=1; g<=gmax; g++)
            t_object obj=objs[idx];

    if(obj.greutate>g)
    {
        dp[idx][g]=dp[idx-1][g];
    }
    else
    {
        int profit1=dp[idx-1][g];
        int profit2 = obj.profit + dp[idx-1][g-obj.greutate];

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