#include <cstdio>

#define MAX_N 5005
#define MAX_G 10005

int dp[MAX_N][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);
    
    dp[0][g[0]] = c[0];
    
    for (int i = 1; i < N; ++i)
        for (int j = 0; j < MAX_G; ++j) {
            dp[i][j] = dp[i - 1][j];
            
            if (j - g[i] >= 0)
               dp[i][j] = max(dp[i][j], dp[i - 1][j - g[i]] + c[i]);
        }
        
    printf ("%d\n", dp[N - 1][G]);
}