#include <fstream>
#define N_MAX 5000 + 1
#define G_MAX 10000 + 1
using namespace std;

int dp[2][G_MAX], profit[N_MAX], weight[N_MAX], N, G;

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

    fin >> N >> G;

    for(int i = 1; i <= N; ++i)
    {
        fin >> weight[i] >> profit[i];
    }


    for(int i = 1; i <= N; ++i)
    {
        bool current = i & 1;
        bool previous = !current;

        for(int j = 1; j <= G; ++j)
        {
            dp[current][j] = dp[previous][j];

            if(j >= weight[i])
            {
                dp[current][j] = max(dp[current][j], dp[previous][j - weight[i]] + profit[i]);
            }
        }
    }

    fout << dp[N & 1][G];
}