#include <cstdio>
#define Gmax 10001

using namespace std;

int main() {
    int N, W, g, p, sol;
    int i, j, v[Gmax];
    sol  = 0;
    v[0] = 0;

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

    scanf("%d%d", &N, &W);
    for (i = 1; i <= N; ++i) {
        scanf("%d%d", &g, &p);
        for (j = W-g; j >= 0; --j) {
            if (v[j+g] < v[j]+p) {
                v[j+g] = v[j]+p;
                //if (v[j+g] > sol)
                 //   sol = v[j+g];
            }
        }
    }

    printf("%d", v[G]);

    return 0;
}