#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

const int Nmax = 5010;
const int Gmax = 10000;

int N , G , i , j;
int g[Nmax] , p[Nmax] , d[2][Gmax];

int main()
{
    freopen("rucsac.in","r",stdin);
    freopen("rucsac.out","w",stdout);

    scanf("%d %d", &N, &G);

    for (i = 1; i <= N; ++i)
        scanf("%d %d", &g[i], &p[i]);

    for (i = 1; i <= N; ++i)
    {
        for (j = 1; j <= G; ++j)
         if (j - g[i] >= 0)
          d[1][j] = max(d[0][j] , d[0][j-g[i]] + p[i]);
         else d[1][j] = d[0][j];

        memcpy(d[0] , d[1] , sizeof(d[1]));
    }

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


    return 0;
}