#include <stdio.h>
#include <stdlib.h>

#define max(x, y) (((x) > (y)) ? (x) : (y))

FILE *read, *write;

int main() {
    read = fopen("rucsac.in", "r");
    write = fopen("rucsac.out", "w");

    int n, g;
    fscanf(read, "%d%d", &n, &g);

    int *answ = (int*)calloc((g + 1), sizeof(int));

    for (int i = 0, x, y; i < n; ++i){ 
        scanf("%d%d", &x, &y);

        for (int j = g; j >= x; --j)
            answ[ j ] = max(answ[ j ], answ[ j - x ] + y);
    }

    fprintf(write, "%d", answ[ g ]);

    return 0;
}