#include <fstream>
using namespace std;

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

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

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

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

    // 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[i][g] = d[i-1][g]; // nu il adaugam
            }
            else
            {
                if (d[i-1][g] > p[i] + d[i-1][g-w[i]]) // daca profitul fara obiectul curent este mai mare decat profitul cu obiectul
                    d[i][g] = d[i-1][g]; // nu il adaugam
                else
                    d[i][g] = p[i] + d[i-1][g-w[i]]; // il adaugam
            }
        }
    }

    out << d[n][G];

    return 0;
}