#include <fstream>
#include <iostream>
#define nmax 10001

using namespace std;

ifstream fin("rucsac.in");
ofstream fout("rucsac.out");

int N,G;
int w[nmax],p[nmax];
int rucs[nmax];

void Citire()
{
    int i;
    fin>>N>>G;
    for(i=1; i<=N; i++)
        fin>>w[i]>>p[i];
}

void Solutie()
{
    int i,j;
    for(i=1; i<=N; i++)
        for(j=G; j>=1; j--)
            if(j>=w[i])
                if(rucs[j]<(p[i]+rucs[j-w[i]]))
                    rucs[j]=p[i]+rucs[j-w[i]];
    fout<<rucs[G];
}

int main()
{
    Citire();
    Solutie();
    return 0;
}