#include <stdio.h>

FILE *fin, *fout;

struct elem {
    int w, p;
}v[5001];

int dp[2][10001];

int max(int a, int b) {
    if(a > b)
        return a;
    return b;
}

int main(void) {
    fin = fopen("rucsac.in", "r");
    int n, g;
    fscanf(fin, "%d%d", &n, &g);
    for(int i = 1; i <= n; ++i)
        fscanf(fin, "%d%d", &v[i].w, &v[i].p);
    fclose(fin);

    for(int i = 1; i <= n; ++i) {
        for(int j = 1; j <= g; ++j) {
            dp[i%2][j] = dp[(i-1)%2][j];
            if(v[i].w <= j)
                dp[i%2][j] = max(dp[i%2][j], dp[(i-1)%2][j - v[i].w] + v[i].p);
        }
    }

    fout = fopen("rucsac.out", "w");
    fprintf(fout, "%d\n", dp[n%2][g]);

    return 0;
}