#include <stdio.h>

using namespace std;
FILE* f, * g;
int gr[10002], p[10002], cost[3][10002];
int main()
{
    int G, n, lp = 1, lc = 0, i, j;
    f = fopen("rucsac.in", "r");
    g = fopen("rucsac.out", "w");
    fscanf(f, "%d %d", &n, &G);
    for (i = 1;i <= n;i++)
        fscanf(f, "%d %d", &gr[i], &p[i]);
    for (i = 1;i <= n;i++)
    {
        for (j = 1;j <= G;j++)
        {
            if (gr[i] <= j)
            {
                if (p[i] + cost[lp][j - gr[i]] > cost[lp][j])
                    cost[lc][j] = p[i] + cost[lp][j - gr[i]];
                else
                    cost[lc][j] = cost[lp][j];
            }
            else
                cost[lc][j] = cost[lp][j];
        }
        lc = 1 - lc;
        lp = 1 - lp;
    }
    /*for(i=0;i<=1;i++)
    {
        for(j=1;j<=G;j++)
            fprintf(g,"%d ",cost[i][j]);
        fprintf(g,"\n");
    }*/
    fprintf(g, "%d\n", cost[lp][G]);
    fclose(f);
    fclose(g);
    return 0;
}