#include <fstream>
using namespace std;

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

int p[10010], w[10010], d[2][10010] = {0};

int main()
{
    int n, G;
    in >> n >> G;

    for (int i = 1; i <= n; ++i)
    {
        in >> w[i] >> p[i];
    }

    int l = 0;
    // d[i][j] = profitul maxim pt primele i obiecte cu limita de greutate j
    for (int i = 1; i <= n; ++i)
    {
        for (int g = 0; g <= G; ++g)
        {
            if (w[i] > g) // daca obiectul are greutatea mai mare ca limita
            {
                d[l][g] = d[1-l][g]; // nu il adaugam
            }
            else
            {
                if (d[1-l][g] > p[i] + d[1-l][g-w[i]]) // daca profitul fara obiectul curent este mai mare decat profitul cu obiectul
                    d[l][g] = d[1-l][g]; // nu il adaugam
                else
                    d[l][g] = p[i] + d[1-l][g-w[i]]; // il adaugam
            }
        }
        l = 1 - l;
    }

    out << d[1][G];

    return 0;
}