#include <stdio.h>

#define MAX 5001
#define MAX_V 10002

using namespace std;

FILE * input = fopen("rucsac.in", "r"), * output = fopen("rucsac.out", "w");

int n,g,maxim,Pmax;

int w[MAX],p[MAX],V[MAX_V];

int i,j;

int main()
{
    fscanf(input, "%i %i", &n, &g);
    for(i=1; i<=n; i++)
    {
        fscanf(input, "%i %i", &w[i], &p[i]);
    }
    for (i=1; i<=n; i++)
        for (j=g-w[i]; j>=0; j--)
            if (V[j+w[i]] < V[j]+p[i])
            {
                V[j+w[i]] = V[j] + p[i];
                if (V[j+w[i]] > Pmax)
                    Pmax = V[j+w[i]];
            }
    fprintf(output, "%i", Pmax);
    return 0;
}