#include <fstream>

using namespace std;

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

int n, g;
int G[10005];
int P[10005];
int V[10005];

int main()
{
    fin >> n >> g;
    for(int i = 1; i <= n; ++i)
        fin >> G[i] >> P[i];

    V[0] = 1;

    for(int i = 1; i <= n; ++i)
    {
        for(int j = g; j >= 1; --j)
        {
            if(j-G[i] != 0)
            {
                if(V[j-G[i]] != 0)
                    if(V[j-G[i]] + P[i] > V[j])
                        V[j] = V[j-G[i]] + P[i];
            }
            else V[j] = P[i];
        }
    }

    fout << V[g] << ' ';
}