#include <algorithm>

#include <climits>

#include <cstdio>

using namespace std;

FILE *f, *g;

bool cmp(float a, float b)
{
    if(a > b)
        return true;

    return false;
}

int n,  i, c[5002], gr[5002], gMax;

int cMax[10001], uz[10001][5002];

int minCost = 0, s;

int j,k ;

int main()
{
    f = fopen("rucsac.in", "r");

    fscanf(f, "%d%d", &n, &gMax);

    for(i = 1; i <= n ;i ++)
        fscanf(f, "%d%d", & gr[i], & c[i]);

    fclose(f);

    for(j = 1; j <= gMax; j ++)
        cMax[j] = -1;

    cMax[0] = 0;

    for(j = 1; j <= gMax; j ++)
        for(i = 1; i <= n; i ++)
        {
            if(cMax[j - gr[i]] != -1 && !uz[j - gr[i]][i])
            {
                if(cMax[j] < c[i] + cMax[j - gr[i]])
                {
                    cMax[j] = c[i] + cMax[j - gr[i]];

                    for(k = 1; k <= n; k ++)
                        uz[j][k] = uz[j - gr[i]][k];

                    uz[j][i] = 1;
                }
            }
        }


    for(i = 1; i <= gMax; i ++)
    {//printf("%d %d\n", cMax[i], minCost);

        if(cMax[i] > minCost)
            minCost = cMax[i];

    }




    g = fopen("rucsac.out", "w");

    fprintf(g, "%d", minCost);

    fclose(g);

    return 0;
}