#include <iostream>
#include <fstream>

using namespace std;
ifstream f("rucsac.in");
ofstream g("rucsac.out");

const int Nmax = 5005, Gmax = 100005;
int n,G,W[Nmax],P[Nmax],DP[2][Gmax];

int main()
{
    f>>n>>G;
    for(int i = 1; i <= n; i++)
    {
        f>>W[i]>>P[i];
    }
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= G; j++)
        {
            if(j-W[i] >= 0) DP[1][j] = max(DP[0][j], DP[0][j-W[i]] + P[i]);
        }
        for(int j = 1; j <= G; j++) DP[0][j] = DP[1][j];
    }
    g<<DP[1][G];
    return 0;
}