#include <stdio.h>
#include <fstream>

#define MAX 5001
#define MAX_V 10002

using namespace std;

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

ifstream input("rucsac.in");
ofstream output("rucsac.out");

int n,g,maxim,Pmax;

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

int i,j;

int main()
{
    //fscanf(input, "%i %i", &n, &g);
    input>>n>>g;
    for(i=1; i<=n; i++)
    {
        //fscanf(input, "%i %i", &w[i], &p[i]);
        input>>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);
    output<<Pmax;
    return 0;
}