#include <stdio.h>

#define G 10000

int ma[3][G+2];

int main()
{
    FILE *fin, *fout;
    int n,gr,i,l,c,g,v;
    fin=fopen("rucsac1.in", "r");
    fscanf(fin, "%d%d", &n, &gr);
    fout=fopen("rucsac1.out", "w");
    for (l=1; l<=n; l++){
        fscanf(fin, "%d%d", &g, &v);
        for (c=1; c<=gr; c++){
            if (c>=g){
                if (ma[1][c]>ma[1][c-g]+v)
                    ma[2][c]=ma[1][c];
                else
                    ma[2][c]=ma[1][c-g]+v;
            }else
                ma[2][c]=ma[1][c];
        }
        for (c=1; c<=gr; c++)
            ma[1][c]=ma[2][c];
    }
    fprintf(fout, "%d\n", ma[2][gr]);
    fclose(fin);
    fclose(fout);
    return 0;
}