#include <cstdio>
#define IN "rucsac.in"
#define OUT "rucsac.out"
#define N 5005
#define G 10005
#include <algorithm>
using namespace std;

int weight[G];
int value[G];
int n,g;

int s1[N],s2[N];

void debug()
{
    for(int i =0 ; i <= g ; i++)
    {
        printf("%d - %d %d\n", i, s1[i],s2[i]);
    }
    printf("\n");
}

int main()
{
    freopen(IN,"r",stdin);
    freopen(OUT,"w",stdout);

    scanf("%d %d",&n,&g);

    for(int i = 0 ; i < n ; i++)
        scanf("%d %d",&weight[i],&value[i]);

    for(int i = 0; i < n; i++)
        {
            for(int j = 1; j <= g; j++)
            {
                s1[j] = s2[j];

                if(weight[i] <= j)
                {
                    s2[j] = max(s1[j], s1[ j - weight[i] ] + value[i]);
                }

            }
            //debug();
        }

        printf("%d", s2[g]);
    return 0;
}