#include <fstream>
#include <algorithm>
using namespace std;

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

struct obiect{
    short w,p;
};

int n, g, i, j, Pmax[10010], maxi;
obiect ob[5010];


int main()
{
    fin >> n >> g;

    for (i = 1; i <= n; ++i)
        fin >> 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];
        }

    fout << maxi;
    return 0;
}