#include<fstream>
#include<stdio.h>
#define Gmax 10010
#define Nmax 5010

using namespace std;
int A[Gmax],p,u,i,j,G[Nmax],P[Nmax],n,g,sol;

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

    fin>>n>>g;

    for(i=1;i<n;i++)

        fin>>G[i]>>P[i];

    for(i=1;i<=n;i++)
        for(j=g;j>=0;j--)
            if( j + G[i] <= g && A[j+G[i]] < A[j] + P[i] )
                A[j+G[i]] =  A[j] + P[i] ;

    sol = 0 ;

    for( i = 1 ; i <= g ; i++ )
        if( A[i] > sol ) sol = A[i] ;


   fout << sol;

    return 0 ;
}