#include <cstdio>
#include <iostream>
using namespace std;

const int nmx = 5002;

int n,g,w[nmx],p[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]);

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

    printf("%d\n", dp[g]);

    return 0;
}