#include <iostream>
#include <fstream>
#include <stdlib.h>

#define max(a,b) (((a) > (b)) ? (a) : (b))

using namespace std;

int profit[2][10001];

int main()
{
    ifstream in("rucsac.in");
    ofstream out("rucsac.out");

    int n, g, greutate, valoare, current=0;
    in >> n >> g;

    in >> greutate >> valoare;
    for (int i = 1;i <= g;i++)
    {
        if (greutate <= i)
            profit[current][i] = valoare;
    }
    current = 1;
    for (int nr = 2;nr <= n;nr++)
    {
        in >> greutate >> valoare;
        for (int i = 1;i <= g;i++)
        {
            if (greutate >= i)
                profit[current][i] = profit[abs(current - 1)][i];
            else
                profit[current][i] = max(profit[abs(current - 1)][i], profit[abs(current - 1)][i - greutate]+valoare);
        }
        
        if (current == 1) current = 0;
        else current = 1;
    }
    out << profit[abs(current - 1)][g];
}