#include <stdio.h>
#include <stdlib.h>
int p[5000], w[5000];
int s[10000];
int main()
{
    FILE*in = fopen("rucsac.in", "r");
    FILE*out = fopen("rucsac.out", "w");
    int n, g, nr, j;
    fscanf(in, "%d %d", &n, &g);
    int i;
    for (i = 0; i < n; i++) {
        fscanf(in, "%d %d", &w[i], &p[i]);
    }
    nr = 0;
    for (i = 0; i < n; i++) {
        for (j = g - w[i]; j >= 1; j--) {
            if (s[j + w[i]] < s[j] + p[i]) {
                s[j + w[i]] = s[j] + p[i];
                if (s[j + w[i]] > nr) {
                    nr = s[j + w[i]];
                }
            }
        }
    }
    fprintf(out, "%d", nr);

    return 0;
}