#include <fstream>
#include <string.h>

using namespace std;

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

int MAX ( int x , int y )
{
    if ( x > y ) { return x ; }
    return y ;
}

short unsigned int n , w , i , j , weight[5005] , value[5005] ;
unsigned int dp[2][10005] ;

int main()
{
    in >> n >> w ;

    for ( i = 1 ; i <= n ; i ++ )
    {
        in >> weight[i] >> value[i] ;
    }

    for ( i = n ; i >= 1 ; i -- )
    {
        for ( j = 0 ; j <= w ; j ++ )
        {
            if ( j >= weight[i] )
            {
                dp[0][j] = MAX( dp[1][j] , value[i] + dp[1][j-weight[i]] ) ;
            }
            else
            {
                dp[0][j] = dp[1][j] ;
            }
        }

        for ( j = 0 ; j <= w ; j ++ )
        {
            dp[1][j] = dp[0][j] ;
        }

        memset ( dp[0] , 0 , w ) ;
    }

    out << dp[1][w] ;

    return 0;
}