#include <fstream>

using namespace std;

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

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

int n , w , i , j , weight[5005] , value[5005] , dp[5005][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 = 1 ; j <= w ; j ++ )
        {
            if ( j >= weight[i] )
            {
                dp[i][j] = MAX( dp[i+1][j] , value[i] + dp[i+1][j-weight[i]] ) ;
            }
            else
            {
                dp[i][j] = dp[i+1][j] ;
            }
        }
    }

    out << dp[1][w] ;

    return 0;
}