/*
    Keep It Simple!
*/

#include <fstream>

using namespace std;

const int kMax_N = 5005;
const int kMax_G = 10005;

int n,g;
int value[kMax_N],weight[kMax_N],dp[kMax_G];

void ReadData()
{
    ifstream fin("rucsac.in");
    fin >> n >> g;
    for(int i=1;i<=n;++i)
        fin >> weight[i] >> value[i];
    fin.close();
}

void PrintResult(int x)
{
    ofstream fout("rucsac.out");
    fout << x;
    fout.close();
}

void Solve()
{
    ReadData();

    for(int i=1;i<=n;++i)
        for(int j = g-weight[i]; j>=0; j--)
            dp[j+weight[i]] = max(dp[j+weight[i]],dp[j]+value[i]);

    int maxvalue = -1;
    for(int i=0;i<=g;++i)
        maxvalue = max(maxvalue,dp[i]);

    PrintResult(maxvalue);
}

int main()
{
    Solve();
    return 0;
}