#include <fstream>
#include <vector>
using namespace std;
int max(int a, int b)
{
    if (a > b) 
        return a;
    else
        return b;
}

int main()
{
    ifstream in("rucsac.in");
    ofstream out("rucsac.out");
    int N, G, i, j,x,sumweight = 0;
    vector<int> W, P;
    W.push_back(0);
    P.push_back(0);

    //citire
    in >> N >> G;
    for (i = 1; i < N+1; ++i)
        in >> x, W.push_back(x), sumweight+=x, in >> x, P.push_back(x);
    int C[N+1][sumweight+1]; 
    for (i = 0; i < N+1; ++i)
        C[i][0] = 0;
    for (i = 0; i < G+1; ++i)
        C[0][i] = 0;

    for (i = 1; i < N+1; i++)
        for ( j = 1; j < G+1; j++)
        {
            if (j - W[i] < 0)
                C[i][j] = C[i-1][j];
            else
                C[i][j] = max(C[i-1][j], C[i-1][j - W[i]] + P[i]);
        }
    /*for (i = 1; i < N+1; i++)
    {
        for (j = 1; j < G+1; j++)
            out << C[i][j] << " ";
        out << endl;
    }*/
    out << C[N][G];
    return 0;

}