#include <cstdio>
#include <algorithm>
using namespace std;
int N, G, Pmax;
int W[5010], P[10010];
int D[2][10010];
int main()
{
    FILE *f=fopen("rucsac.in","rt");
    FILE *g=fopen("rucsac.out","wt");
    fscanf(f,"%d%d", &N, &G);
    for(int i = 1; i <= N; ++i)
        fscanf(f,"%d%d", &W[i], &P[i]);
    int l=0;
    for(int i = 1; i <= N; ++i, l = 1 - l)
        for(int cw = 0; cw <= G; ++cw)
            {
                    D[1-l][cw] = D[l][cw];
                    if(W[i] <= cw)
                        D[1-l][cw] = max(D[1-l][cw], D[l][cw - W[i]] + P[i]);
            }
    fprintf("%d\n", D[l][G]);
    return 0;

    }