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

typedef struct
{
    int g,v;
}item;
item r[10001]; int s [10001][10001];
int main()
{
    FILE *fin = fopen("rucsac.in","r"),*fout = fopen ("rucsac.out","w");
    int n, gmax; fscanf(fin,"%d%d",&n,&gmax);
    for(int i = 0 ; i < n ; ++i)
        fscanf(fin,"%d%d",&r[i].g,&r[i].v);
    for(int j = r[0].g; j <= gmax; ++j)
        s[0][j] = r[0].v;
    for(int i = 1 ; i < n ; ++i)
        for(int j = r[i].g; j<=gmax;++j)
            {
                if(j-r[i].g >= 0 && r[i].v + s[i-1][j-r[i].g] > s[i-1][j])
                    {
                        s[i][j] = r[i].v + s[i-1][j-r[i].g];
                    }
                else
                {
                    s[i][j] = s[i-1][j];
                }
            }
 /*    for(int i = 0 ; i < n ; ++i){
        for(int j = 0; j<=gmax;++j)
            printf("%d ", s[i][j]);
            printf("\n");}*/
    fprintf(fout,"%d\n",s[n-1][gmax]);


    return 0 ;
}