#include <cstdio>
#define max(a,b) (a > b ? a : b)
#define min(a,b) (a < b ? a : b)

using namespace std;

const int nmx = 5002;

int n,g,p[nmx],w[nmx],dp[2*nmx];

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

    scanf("%d %d", &n ,&g);
    for(int i = 1; i <= n; ++i)
        scanf("%d %d", &w[i], &p[i]);

    dp[0] = 0;

    int tw = 0,maxim = -1;
    for(int i = 1; i <= n; ++i){
        tw += w[i];
        tw = min(tw,g);
        for(int j = tw; j >= w[i]; --j)
            if(dp[j-w[i]] + p[i] > dp[j])
                dp[j] = dp[j-w[i]] + p[i];
    }

    for(int i = 1; i <= g; ++i)
        maxim = max(maxim,dp[i]);

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

    return 0;
}