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

#define MAXN 5001
#define MAXG 10001

int w[MAXN], p[MAXN];
int v[2][MAXG];

int max(int *a, int *b){
    return *a>*b ? *a:*b;
}

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

    int i1, i2;
    for (int i=1; i<=n; i++){
        i1=i%2;
        i2=(i+1)%2;
        for (int j=0; j<=g; j++){
            v[i1][j]=v[i2][j];
            if (w[i]<=j){
                int x=v[i2][j-w[i]]+p[i];
                v[i1][j]=max(&v[i1][j], &x);
            }
        }
    }
    fprintf(fout, "%d", v[i1][g]);
    return 0;
}