#include<iostream>
#include<fstream>
#define maxn 5001
#define maxg 10001

using namespace std;

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

int W[maxn], P[maxn];
int OP[maxg];

int main()
 {
    int N, G;
    f>>N>>G;
    for (int i = 1; i <= N; ++i)
        f>>W[i]>>P[i];
    int sol = 0;

    for( int i = 1; i <= N; ++i)
        for( int j = G - W[i]; j >= 0; --j)
        {
            if( OP[j+W[i]] < OP[j] + P[i] )
            {
                OP[j+W[i]] = OP[j] + P[i];
                if( OP[j+W[i]] > sol)
                    sol = OP[j+W[i]];
            }
        }
    g<<sol;
    return 0;
}