#include <stdio.h>

int main()
{
    int n, G, i, j;
    int g[5001], c[5001];
    int cmax[2][10001];

    FILE *fin = fopen("date.in", "r");
    fscanf(fin, "%d %d", &n, &G);

    for (i = 1; i <= n; i++)
        fscanf(fin, "%d %d", &g[i], &c[i]);
    fclose(fin);

    for (j = 0; j <= G; j++)
        cmax[0][j] = 0;

    for (i = 1; i <= n; i++)
    {
        for (j = 0; j <= G; j++)
        {
            if (g[i] > j)
            {
                cmax[i % 2][j] = cmax[(i - 1) % 2][j];
            }
            else
            {
                if (c[i] + cmax[(i - 1) % 2][j - g[i]] > cmax[(i - 1) % 2][j])
                {
                    cmax[i % 2][j] = c[i] + cmax[(i - 1) % 2][j - g[i]];
                }
                else
                {
                    cmax[i % 2][j] = cmax[(i - 1) % 2][j];
                }
            }
        }
    }

    printf("%d\n", cmax[n % 2][G]);

    return 0;
}