#include <stdio.h>
FILE *fin, *fout;
int n, g, *v1, *v2;
struct obiect
{
       int valoare;
       int greutate;
} *input;
int max(int a, int b)
{
    return (a>b)?a:b;
}
int main()
{
    fin = fopen("rucsac.in", "r");
    fout = fopen("rucsac.out", "w");
    fscanf(fin, "%d%d", &n, &g);
    input = new obiect[n];
    for(int i =0; i< n; i++) fscanf(fin, "%d%d", &input[i].greutate, &input[i].valoare);
    v1 = new int[g+3];
    v2 = new int[g+3];
    for(int i =0; i<= g; i++) {v1[i] = 0;v2[i] = 0;}
    for(int i = 1; i<= n; i++)
    {
            for(int j = 1; j<= g; j++)
            {
                    if(input[i-1].greutate > j) {v2[j] = v1[j];continue;}
                    v2[j] = max(v1[j - input[i-1].greutate] + input[i-1].valoare, v1[j]);
            }
            for(int j = 1; j<= g; j++) v1[j] = v2[j];
    }
    fprintf(fout, "%d\n", v1[g]);
    fclose(fin);
    fclose(fout);
    return 0;
}