/*  Se da o multime formata din N obiecte, fiecare fiind caracterizat de o greutate si un profit.
Sa se gaseasca o submultime de obiecte astfel incat suma profiturilor lor sa fie maxima,
iar suma greutatilor lor sa nu depaseasca o valoare greutate. */
//    O(N*G)

#include <fstream>

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

int n,greutate,gr[5050],pr[5050],d[2][500];


int main()
{
    f>>n>>greutate;
    for (int i=1; i<=n; ++i) f>>gr[i]>>pr[i];
    int l=2;
    for (int i=1; i<=n; ++i)
    {
        for (int j=1; j<=greutate; ++j)
        {
            // nu il sutesc pe i
            d[l][j]=d[3-l][j];
            // il sutesc pe i daca pot, si daca se merita
            if (gr[i]<=j) d[l][j]=max(d[l][j], d[3-l][j-gr[i]]+pr[i]);
        }
        l=3-l;
    }
    g<<d[3-l][greutate]<<'\n';
    f.close();
    g.close();
    return 0;
}