#include <cstdio>
#include <algorithm>
using namespace std;
const int NMAX = 5000;
const int GMAX = 10000;
int w[NMAX], p[NMAX], dp[GMAX];
int rucsac(int n, int g){
    int i, j, max1 = 0;
    for (i = 1; i <= n; i ++)
        for (j = g - w[i]; j >= 0; j --){
            dp[j + w[i]] = max(dp[j + w[i]], dp[j] + p[i]);
            max1 = max(max1, dp[j + w[i]]);
        }
    return max1;
}
int main(){
    freopen("rucsac.in", "r", stdin);
    freopen("rucsac.out", "w", stdout);
    int n, g, i;
    scanf("%d%d", &n, &g);
    for (i = 1; i <= n; i ++)
        scanf("%d%d", &w[i], &p[i]);
    printf("%d\n", rucsac(n, g));
    return 0;
}