#include <cstdio>
#include <algorithm>

#define NMAX 5001
#define GMAX 10001

using namespace std;

int N, G;
int a[2][GMAX];


int main()
{
    int i, j, l;
    int w[NMAX], v[NMAX];

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

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

    for(i=0;i<N;++i)
    {
        scanf("%d %d", &w[i], &v[i]);
    }

    l = 1;

    for(j=0;j<N;++j, l = 1-l)
    {
        for(i=0;i<=G;++i)
        {
            a[l][i] = a[1-l][i];

            if(w[j] <= i)
            {
                a[l][i] = max(a[l][i], a[1-l][i-w[j]] + v[j]);
            }
        }
    }


    printf("%d", a[1-l][G]);

    return 0;
}