#include <fstream>
using namespace std;
ifstream f("rucsac.in");
ofstream g("rucsac.out");
struct OBIECT{
    int g, val;
}V[5001];
int N, A[5001][10001];
int DP(int poz, int g){
    if(poz > N)
        return 0;
    if( A[poz][g] > 0 )
        return A[poz][g];
    int x1, x2;
    x1 = DP(poz+1,g);//nu iau obiectul
    if(g >= V[poz].g )//verific daca il pot lua
        x2 = DP(poz+1,g-V[poz].g) + V[poz].val;
    else
        x2 = -1;
    if( x1 < x2 )
        x1 = x2; //salvez in x1 val maxima
    A[poz][g] = x1;
    return x1;
}

int main()
{
    int i, j, gmax;
    f >> N >> gmax;
    for(i = 1; i <= N; i++)
        f >> V[i].g >> V[i].val;
    g << DP(1, gmax);
    return 0;
}