#include <fstream>
#include <iostream>
#include <algorithm>

using namespace std;

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

struct obiect{
    int greutate;
    int profit;
};

struct obiect v[5005];

int dp[10005];

void citire(int &N, int &G)
{
    fin>>N;
    fin>>G;
    for(int i=0; i<N;i++)
    {
        fin>>v[i].greutate;
        fin>>v[i].profit;
    }
}

int ProfitMax(int dp[], int G, int N)
{
    for(int i=1; i<v[0].greutate; i++)
    {
        dp[i]=0;
    }
    for(int j=v[0].greutate; j<=G; j++)
    {
        dp[j]=v[0].profit;
    }

    for(int i=1; i<N; i++){
        for(int j=G; j>=v[i].greutate; j--)
        {
            dp[j]=max(dp[j], (dp[j-v[i].greutate]+v[i].profit));
        }
    }

    return dp[G];
}

int main()
{
    int N, G;
    citire(N,G);
    fout<<ProfitMax(dp,G,N);
    return 0;
}