#include <cstdio>
#include <algorithm>

using namespace std;

#define MAXN 5002
#define GMAX 10002
int N, G, Pmax;
int W[MAXN], P[MAXN];
//int D[MAXN][MAXG];
int Sol[GMAX];

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

    /// Citire
    scanf("%d %d", &N, &G);
    for(int i = 1; i <= N; ++i)
        scanf("%d %d", &W[i], &P[i]);
    for(int i = 1; i <= N; ++i)
        for(int j = G-W[i]; j >= 0; --j)
        {
            if( Sol[j+W[i]] < Sol[j] + P[i] ){
                Sol[j+W[i]] = Sol[j] + P[i];
              Pmax = max (Pmax, Sol[j + W[i]]);
            }
        }

    printf("%d\n", Pmax);

    return 0;
}