#include <cstdio>
#include <cstring>

#define MAX_N 5005
#define MAX_G 10005

int dp1[MAX_G], dp2[MAX_G];
int c[MAX_N], g[MAX_N];
int N, G;

inline int max (int a, int b) {
       return (a > b) ? a : b;
}

int main () {
    freopen ("rucsac.in", "r", stdin);
    freopen ("rucsac.out", "w", stdout);
    
    scanf ("%d %d", &N, &G);
    for (int i = 0; i < N; ++i) 
        scanf ("%d %d", g + i, c + i);
    
    dp1[g[0]] = c[0];
    
    for (int i = 1; i < N; ++i) {
        for (int j = 0; j < MAX_G; ++j) {
            dp2[j] = dp1[j];
            
            if (j - g[i] >= 0)
               dp2[j] = max(dp2[j], dp1[j - g[i]] + c[i]);
        }
        
        memcpy (dp1, dp2, sizeof (dp2));
    }
        
    printf ("%d\n", dp2[G]);
}