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

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

int main(void)
{
    int N, G;
    int greutate[5001], profit[5001];
    int a[10001] = {0};

    FILE*fin=fopen("rucsac.in","rt");
    FILE*fout =fopen("rucsac.out","wt");

    if (fscanf(fin,"%d %d",&N,&G) != 2) {
        perror("Eroare la citire");
        exit(1);
    }

    for (int i=1;i<=N;i++) {
        fscanf(fin,"%d %d",&greutate[i],&profit[i]);
    }

    for(int i=1;i<=N;i++) {
        for (int w = G; w >= greutate[i]; w--) {
            a[w] = max(a[w], a[w - greutate[i]] + profit[i]);
        }
    }

    fprintf(fout, "%d\n", a[G]);
    fclose(fin);
    fclose(fout);
    return 0;
}