#include <fstream>
#include <algorithm>
#define obiect pair<int, int>
#define w first
#define p second
using namespace std;

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

int N, G, i = 1, j, Pmax[10010], maxi;
obiect ob[5010];


int main()
{
    f >> N >> G;

    for (i = 1; i < N; ++i)
        f >> ob[i].w >> ob[i].p;

    for (i = 1; i <= N; ++i)
        for (j = G; j >= ob[i].w; --j)
        {
            Pmax[j] = max(Pmax[j], Pmax[j - ob[i].w] + ob[i].p);
            if (Pmax[j] > maxi)
                 maxi = Pmax[j];
        }

    g << maxi;
    return 0;
}